Логические задачи : Задачи от MIT

	"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.
Задачи на логику и сообразительность
Главная \| О проекте \| Все задачи-1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C \| Добавить задачу

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

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

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

запомнить меня

Задачи

Переливания и взвешивания

Теорвер, комбинаторика

Задания на наблюдательность

требуется помощь

Чисто поржать

Детские с подковыркой

Данетки

Текущие:

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

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

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

Справочная

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

Реклама

Версия для смартфонов

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

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

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


+ -1 -

Ответ

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

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

ответов: 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 пишет:

Хм... :)) Переносов и проверок, естественно, нет? А эн является степенью двойки или надо считать произвольным?

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

Обсуждаем

Задача Разрезанный треугольник:
http://lprobs.ru/img/yes.gif : [скрыто]
Гостевая книга:
не представился : Это было в 1913 году. Одиннадцатилетняя девочка, пансионерка Московской Ржевской гимназии очень прос...
Задача Гора.:
Xuzke : [скрыто]
Гостевая книга:
не представился : В школе все казалось правильным. Из математики следует физика, из физики следует химия, из химии сле...
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...

Реклама

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

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

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

Задачи

Данетки

Справочная

Реклама

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

Ответ

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

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

Обсуждаем

Реклама