"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

Задачи на логику и сообразительность




О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!


Справочная



Признаки делимости
Площади фигур


Реклама






задача: Задачи от MIT

Задачу прислал: Админ


Сложность: простаяВ ваших руках компьютер с n-битным машинным словом, поддерживающий стандартные бит операции: AND, OR, NOT, XOR, LEFT SHIFT, RIGHT SHIFT. Сколько битовых операций вам понадобится для определения числа установленных в единицу бит в машинном слове w? Можно считать доступным любое нужное количество регистров и бесплатной операцию COPY. Результат должен быть получен в форме целого числа представленного машинным словом.



Ответ





Решение задачи





Ваши ответы на задачу


ответов: 4

KoKos 2016-07-27 17:45:14 пишет:
Хм. :) Ну если уточнений нет, то полагаем в лоб, с удобными допущениями.

w->b; b->a; a&1; a->r1 (1 операция)
b>>1; b->a; a&1; a->r2 (2 операции)
b>>1; b->a; a&1; a->r3 (2 операции)
... и так до rN - соответственно, 2*N-1 операция на подготовку, после которых получаем все биты числа раскиданные по младшим битам регистров. Остается просуммировать регистры, чтобы подсчитать количество единиц.

а=r1^r2; r2=(r2&r1)<<1; r1=а^r2; (4 операции, и в r1 готова сумма первых двух битов)
а=r1^r3; r3=(r3&r1)<<1; r1=а^r3; (опять хватит 4х операций, битов максимум три, сноса в третий разряд пока можно не предусматривать)
а=r1^r4; r4=(r4&r1)<<1; (а вот теперь нам грозит лишний снос, так что цепочка будет длиннее) r1=a; а=r1^r4; r4=(r4&r1)<<1; r1=а^r4; (итого операций уже 7, и традиционно в r1 накоплена сумма битов - теперь до r7 включительно будет по 7 операций, потом до r15 - по 10 и т.д.)

И так далее, N раз по 3*K+1 операций. Можно попробовать это веселое дело еще пооптимизировать, но тут уже без уточнений условия никуда... А то окажется потом, что константой 1 пользоваться нельзя - и все нафиг надо пересчитывать. 8)))

ivana2000 2016-07-27 15:52:12 пишет:

Пример сложения.

A = 0011101
B = 0110101

Складываем «в столбик».

0110101
0011101
–––––––
1010010

Пример реализации сумматора.

AND              XOR
0011101         0011101
0110101         0110101
–––––––         –––––––
0010101         0101000

LSHIFT
0101010

AND              XOR
0101010         0101010
0101000         0101000
–––––––         –––––––
0101000         0000010

LSHIFT
1010000

AND              XOR
1010000         1010000
0000010         0000010
–––––––         –––––––
0000000         1010010

...........................
...........................
До тех пор, пока LSHIFT не будет применен n раз.
...........................
...........................

Вроде, получилось то же самое.

Операцию A' = XOR(A,B) можно назвать «недоразвитым» сумматором. Она арифметически правильно складывает биты, но не учитывает перенос из предыдущего разряда. Для этого используется операция
B" = AND(A,B).
Единицы числа B" нужно арифметически прибавить к следующим разрядам числа A'. А для этого B" нужно сдвинуть на один разряд влево, т.е. получится
B' = LSHIFT(B",1).
Продолжаем то же самое с числами A' и B', пока сдвиг влево не будет применен n раз. При этом B' наверняка станет равным нулю.
Не уверен, что все правильно, но, наверное, подобным образом сумматор все же можно реализовать.

Ну, считаем, что сумматор есть.

Делаем маску на младший разряд.
M2 = M1
M1 = NOT(M1)
M1 = OR(M1,M2)
M = RSHIFT(M1,n-1).

Обнуляем сумматор.
S = XOR(S).

Следующую последовательность выполняем n раз.
Выделяем младший разряд A.
D = AND(A,M)
Отправляем D в «сумматор».
Складываем D и S.
Сдвигаем A на разряд вправо.
A = RSHIFT(A,1).

Ну, это «лобовое» решение, конечно, т.к. алгоритм с сумматором ясен изначально.
А что, есть какой-то красивый «фокус» без организации сумматора?

KoKos 2016-07-26 19:01:16 пишет:
А, да - еще вопрос. Если уж сдвиги без переноса - то они циклические? Или с потерей битов?

KoKos 2016-07-26 18:57:16 пишет:
Хм... :)) Переносов и проверок, естественно, нет? А эн является степенью двойки или надо считать произвольным?

Добавьте комментарий:
Автор:

Комментарий:

Пожалуйста, введите символы с картинки:
(подтверждение не требуется для зарегистрированных пользователей)



 





Обсуждаем

  Задача Квадрат 4x4:
R-2 : [скрыто]
KoKos : [скрыто]
Задача Дефект масс:
R-2 : [скрыто]
Задача Квадрат 4x4:
R-2 : [скрыто]
Задача Дефект масс:
ivana2000 : [скрыто]
Задача Квадрат 4x4:
ivana2000 : [скрыто]
Задача Два момента:
Vladius : [скрыто]
Задача Расставить знаки математических операций:
Вика : [скрыто]
Задача Вопросительное предложение:
Vladius : [скрыто]
Задача Задача про рабочих:
Vladius : [скрыто]
Vladius : [скрыто]
Задача 1 рубль = 1 копейке:
Vladius : [скрыто]
Задача Вот в полу открылся люк ...:
bobo : [решил задачу]
Задача Квадрат 4x4:
не представился : [скрыто]
Задача Дефект масс:
R-2 : [скрыто]



Реклама



© 2009-201x Логические задачи