?

Log in

задачки про биты (для программистов) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачки про биты (для программистов) [янв. 12, 2008|03:49 am]
Anatoly Vorobey
1. Что делает функция g(x)? Зачем она нужна? x - положительное целое число.

f(x) = x & -x
h(x) = x + f(x)
g(x) = (((h(x) xor x)/f(x)) >> 2) + h(x)


2. 64-битное число содержит восемь ASCII-символов, по одному в каждом байте. Дано, что каждый из этих символов либо пробел, либо цифра, либо латинская буква. Произведите над всеми символами операцию toupper() (переводящую строчные буквы в прописные) с помощью всего трех битовых операций над исходным числом. Битовой операцией, определенности ради, назовем одно из двух: a) любую операцию с одним или двумя аргументами, значение которой в каждом бите результата зависит только от соответствующих битов аргументов; b) сдвиг влево или вправо.

(update: первоначально я забыл разрешить b) выше, виноват)
СсылкаОтветить

Comments:
[User Picture]From: spamsink
2008-01-12 02:19 am
1. A057168 - Cute.
2. Пока только 4 получается.
(Ответить) (Thread)
[User Picture]From: spamsink
2008-01-12 02:35 am
HAKMEM читаешь?
(Ответить) (Thread)
[User Picture]From: spamsink
2008-01-12 03:01 am
2. Четыре, хоть ты дерись:
map { print chr($_ & ~($_ & 0100) >> 1); } (32, 48..57, 65..90, 97..123);
(Ответить) (Thread)
[User Picture]From: nevsky
2008-01-12 03:14 am
Вроде можно вместо сдвига и инверсии вычесть 1.

А что такое A057168?
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2008-01-12 03:16 am
Так просили же битовые операции.

Это чтобы avva знал, что я догадался, а остальные могли подумать.
(Ответить) (Parent) (Thread)
From: qaraabayna
2008-01-12 03:48 am
Для автора работающего в гугле, вопрос "что такое" является провокационным.
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 03:39 am
Результат сдвига зависит не от соответствующих битов аргумента.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2008-01-12 03:50 am
Смотря как определить соответствие. Важно, что каждый бит сдвига на константу зависит ровно не более чем от одного бита сдвигаемого аргумента, а соответствие между битом аргумента и битом результата определяется размером сдвига.
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 04:23 am
Тогда непонятно, с чего вдруг "ровно не более чем от одного бита" — в задаче написано "значение которой в каждом бите результата зависит только от соответствующих битов аргументов".
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2008-01-12 04:25 am
Аргументов может быть два.
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 04:43 am
И?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2008-01-12 10:23 am
Это я виноват, как обычно. Слишком строго определил, не подумав. Сдвиг тоже традиционно является битовой операцией, хотя под это определение не подпадает. Извините, сейчас исправлю.
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2008-01-12 08:28 am
Да, черт побери!

Все-таки три: вместо энд и инверсии используем функцию, которая является их комбинацией.
(Ответить) (Parent) (Thread)
[User Picture]From: spamsink
2008-01-12 08:31 am
А, черт, надо было на Верилоге писать! :)
(Ответить) (Parent) (Thread)
[User Picture]From: softmaster
2008-01-12 03:31 pm
сорри, а что за битовая функция такая?
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2008-01-13 02:14 pm
Я не знаю, как она называется, но могу нарисовать ее таблицу истинности. Требования ведь не было, чтобы у функции название было, правильно? :)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-12 10:22 am
Это три, как тебе уже указали :-)
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 03:13 am
1. Последовательное приложение g(x) гоняет единички влево по слову, сохраняя их количество.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 10:20 am
Не совсем.
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 02:12 pm
Совсем.
(Ответить) (Parent) (Thread)
[User Picture]From: pinkoflamingo
2008-01-12 02:20 pm
OK, если внятно писать, то перебирает все слова с количеством единиц как в исходном слове, по возрастанию.
(Ответить) (Parent) (Thread)
From: qaraabayna
2008-01-12 03:46 am
1. Округляет до большей степени двойки
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 10:20 am
Не совсем.
(Ответить) (Parent) (Thread)
From: qaraabayna
2008-01-12 01:48 pm
Забыл сказать - той степени для которой нужно округление
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2008-01-12 08:17 am
1. - не понял, в какой системе представления знака? Если 1's complement, то f == 0, h == Id, g == h == Id
2. если бы не цифры, хватило бы одной. Будем думать, что делать с цифрами (видимо, надо придумать такой f и f^-1, чтобы посредине можно было сделать or с соотв. маской).
(Ответить) (Thread)
[User Picture]From: faceted_jacinth
2008-01-12 09:51 am
лол
f == "самый младший ненулевой разряд", вообще-то.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-12 10:20 am
1. 2's complement, как весь мир давно :-)
(Ответить) (Parent) (Thread)
[User Picture]From: pilpilon
2008-01-12 11:23 am
1.берет самую младшеразрядную группу единиц. старшую сдвигает влево, остальные до упора вправо.
2. за две операции:
(((X xor A) and B) xor A)
где А - учетверенный пробел, В -его обращение.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 11:50 am
1. Верно. А зачем это нужно?
2. нет, это что-то не то
(Ответить) (Parent) (Thread)
[User Picture]From: pilpilon
2008-01-12 01:41 pm
дя перебора всех чисел с данным числом единиц?

2.да, у меня странная была идея что это можно сделать без сдвигов, какой-то бред написал.
можно :
С = 01000000010000000100000001000000
F(X): X & C
G(X) : ~(X >>1)
H(X) : X & F(G(X))
(Ответить) (Parent) (Thread)
[User Picture]From: pilpilon
2008-01-12 01:31 pm
чего-то я странное написал
(Ответить) (Parent) (Thread)
[User Picture]From: neatfires
2008-01-12 11:35 am
1. счеты? :)
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 11:49 am
В каком-то смысле, да :-)
(Ответить) (Parent) (Thread)
[User Picture]From: neatfires
2008-01-12 01:38 pm
Может, state machine для перебора всех вариантов расстановки определенного количества единиц и нулей (начиная с заданного state)? Если начать с x=00000111 и последовательно печатать g(x), g(g(x)), g(g(g(x))) итд., пока не упремся в 11100000, то функция переберет все варианты.
(Ответить) (Parent) (Thread)
[User Picture]From: neatfires
2008-01-12 07:21 pm
ОК. Запишите мне это в счет будущего (жаль, нескоро) интервью :Р
(Ответить) (Parent) (Thread)
From: qehgt
2008-01-12 11:54 am
>(update: первоначально я забыл разрешить b) выше, виноват)
А я уже решил, что совсем квалификацию потерял. С этим пунктом в 3 "операции" всё укладывается, конечно же.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 12:38 pm
Ага. Извините :)
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2008-01-12 12:41 pm
Что-то не то. Например, h(x) у вас вычислено неправильно, а h(x) ^ x уже правильно, хотя должно было дать неверный результат из-за ошибки в h(x) :)

И непонятно, зачем нужна такая g(x).,
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2008-01-12 01:08 pm
x = 1010111000 (10 бит)
f(x) = 1000
h(x) = f(x) + x = 1011000000 (у вас 1011110000, результат сложения с 111000, а не с 1000)
h(x) ^ x = 0001111000, у вас получилось так же, хотя должно было получиться 1011110000 ^ 1010111000 = 0001001000. Как это так вышло? :)

Отсюда значение g(x) должно выйти выходит неверным, если вы не подставили в конце опять правильное h(x) вместо своего неправильного :) (и да, у нее есть более полезное применение).
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2008-01-12 02:03 pm
:)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-12 02:03 pm
не совсем.
(Ответить) (Parent) (Thread)
From: qaraabayna
2008-01-12 01:46 pm
Сырого материала слишком много, чтобы задачка была интересной
(Ответить) (Thread)
[User Picture]From: baramin
2008-01-12 05:49 pm

1ая задача

g(x) - выделяет младшую единицу в бинарном представлении (пусть это k-ая единица).
g(XXXXXXXX1<--k нулей-->) = 1<--k нулей-->

h(x) - зануляет младшую непрерывную последовательность единиц (начиная с k-ого разряда) в бинарном представлении и выставляет 1 в первый промежуток за последовательностью единиц.
h(XXXX0<--m единиц--><--k нулей-->) = XXXX1<--(k+m) нулей-->

z(x)=(((h(x) xor x)/f(x)) >> 2) - последовательность единиц за k-ым разрядом, спущенная до начала слова
z(XXXX0<--m единиц--><--k нулей-->) = <--(m-1) единиц-->

g(XXXX0<--m единиц--><--k нулей-->) = XXXX1<--(k+1) нулей--><--(m-1) единиц-->

g(x) сохраняет количество 1 и 0 :)
(Ответить) (Thread)
[User Picture]From: baramin
2008-01-12 06:18 pm

Re: 1ая задача

Возрастающий шейкер для 1 и 0?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-13 12:10 pm

Re: 1ая задача

:)
(Ответить) (Parent) (Thread)
[User Picture]From: master_nemo
2008-03-16 01:42 pm

блин сто лет не брал в руки шашек. и зачем сейчас вот по

только четыре:
x:= x and not ((x shr 1) and c);
не знаю я как AND NOT записать в 1 функцию
я помню как надо мной смеялись когда я такую фигню с флагами в WINAPI проделывал, но ведь работало!
А если есть какой безумный способ преобразовать все к 3м операциям через эквивалентные преобразования то я этим извращением сейчас заниматься не буду :)
(Ответить) (Thread)
[User Picture]From: master_nemo
2008-03-16 01:47 pm

upd fix

где С:={8 пробелов}
(Ответить) (Parent) (Thread)