Найдите количество чисел, таких, что в записи в двоичной системе счисления используется ровно 2 единицы

@Axel_kz1996 · Регистрация: 24.04.2011

Author24 — интернет-сервис помощи студентам

нужно сделать до завтра
Найдите количество чисел Z, удовлетворяющих неравенству A ≤ Z ≤B, таких, что в записи Z в двоичной системе счисления используется ровно 2 единицы. Например, если A=10; B=20; то таких чисел 5 (это числа 10=10102; 12=11002; 17=100012; 18=100102; 20=101002).

Формат входных данных
На вход программы поступают два числа, записанных через пробел — A, B ( 0 ≤ A, B ≤ 109)

Формат выходных данных
Выведите одно число – количество чисел Z.

@Puporev · 20.04.2012, 20:50

Сообщение от Axel_kz1996

B ≤ 109

наверное 10^9

Добавлено через 41 минуту
Как считать единицы написано здесь
http://algolist.manual.ru/olimp/ar_prb.php
Задача 5, нажать решение.
Вот код программы с этим алгоритмом, правда быстро считает только до 10^7, дальше тормозит.

Pascal

uses crt;
var a,b,i,j,x,k:longint;
begin
clrscr;
writeln('Введите 2 натуральных числа a<b:');
readln(a,b);
k:=0;
for i:=a to b do
 begin
  x:=i;
  j:=0;
  while x<>0 do
   begin
    x:=(x-1)and x;
    inc(j);
   end;
  if j=2 then inc(k);
 end;
write('k=',k);
readln
end.

valeriikozlov · 21.04.2012, 06:09

Axel_kz1996, проверяйте:

Pascal

var
  a,b,minn,maxx,col:longint; 
procedure proc(a:longint);
var t:longint;
begin
t:=1; minn:=0; maxx:=0;
while a>0 do begin
if (a mod 2) = 1 then begin
minn:=maxx; maxx:=t;
end;
a:=a div 2;
inc(t);
end;
if minn=0 then begin
minn:=maxx-2; dec(maxx);
end;
end;
 
function func():longint;
var i, res:longint;
begin
if minn<1 then func:=0
else
begin
res:=minn;
for i:=maxx-1 downto 2 do
res:=res+i-1;
func:=res;
end;
end;
 
begin
 read(a,b);
 proc(a-1);
 col:=col-func();
 proc(b);
 col:=col+func();
 writeln(col); 
 end.

@Puporev · 21.04.2012, 08:04

Круто, хоть и не понятно...

valeriikozlov · 21.04.2012, 12:25

Сообщение от Puporev

Круто, хоть и не понятно...

Тут реализовано всего две идеи:
1. Подсчитать сколько чисел имеют ровно две единицы в числах в диапазоне от 0 до A-1. Подсчитать сколько чисел имеют ровно две единицы в числах в диапазоне от 0 до B. Вычесть из второго первое, это и будет ответ.
2. Сам подсчет чисел имеющих ровно две единицы в числах в диапазоне от 0 до X:
при переводе в двоичную систему числа может получится 2 варианта - когда в числе единиц 2 и более, и когда единиц всего одна. Когда единиц две и более нас интересует месторасположение самой левой единицы и следующей за ней самой левой единицы. Например вот такое двоичное число:
101101100 - то здесь maxx=9, minn=7. Числа которые нас интересуют, будут такими:
101000000
100100000
100010000
...

Pascal

1	res:=minn;

затем будут такими:
11000000
10100000
10010000
...
потом такими:
1100000
1010000
1001000
...

Pascal

1 2	for i:=maxx-1 downto 2 do res:=res+i-1;

Если вдруг число оказывается с одной единицей, например такое:
10000000 (maxx=8, minn=0)
то, числа которые нас интересуют, будут такими:
1100000
1010000
...
Для этого:

Сообщение от valeriikozlov

if minn=0 then begin
minn:=maxx-2; dec(maxx);
end;

Если вдруг minn оказывается <1, то количество интересующих нас чисел равно 0.

@AshGir · 23.10.2018, 16:17

Переберем позиции двух единиц в битовой записи искомого числа. Потом переведем в двоичную запись и проверим, что число больше A и меньше B. Дополнительно надо заметить, что во всех возможных числах не более 32 бит.

a,b=map(int, input().split())

c=0

for i in range((len(bin(a)))-3,(len(bin(b)))-2):

for j in range(i):

if 2**j+2**i>=a and 2**j+2**i<=b:

c+=1

print(c)

@Axel_kz1996 20 / 20 / 9 Регистрация: 24.04.2011 Сообщений: 54
		1
	Найдите количество чисел, таких, что в записи в двоичной системе счисления используется ровно 2 единицы 20.04.2012, 19:44. Показов 5762. Ответов 5 Метки нет (Все метки) нужно сделать до завтра Найдите количество чисел Z, удовлетворяющих неравенству A ≤ Z ≤B, таких, что в записи Z в двоичной системе счисления используется ровно 2 единицы. Например, если A=10; B=20; то таких чисел 5 (это числа 10=10102; 12=11002; 17=100012; 18=100102; 20=101002). Формат входных данных На вход программы поступают два числа, записанных через пробел — A, B ( 0 ≤ A, B ≤ 109) Формат выходных данных Выведите одно число – количество чисел Z. 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	21.04.2012, 08:04	4
	Круто, хоть и не понятно... 0

@AshGir 3 / 3 / 1 Регистрация: 11.08.2018 Сообщений: 9
	23.10.2018, 16:17	6
	Переберем позиции двух единиц в битовой записи искомого числа. Потом переведем в двоичную запись и проверим, что число больше A и меньше B. Дополнительно надо заметить, что во всех возможных числах не более 32 бит. a,b=map(int, input().split()) c=0 for i in range((len(bin(a)))-3,(len(bin(b)))-2): for j in range(i): if 2j+2i>=a and 2j+2i<=b: c+=1 print(c) 0