задачки про биты (для программистов)

[avva]

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

[spamsink.livejournal.com]

1. A057168 - Cute.
2. Пока только 4 получается.

[spamsink.livejournal.com]

HAKMEM читаешь?

[spamsink.livejournal.com]

2. Четыре, хоть ты дерись:
map { print chr($_ & ~($_ & 0100) >> 1); } (32, 48..57, 65..90, 97..123);

[nevsky.livejournal.com]

Вроде можно вместо сдвига и инверсии вычесть 1.

А что такое A057168?

[spamsink.livejournal.com]

Так просили же битовые операции.

Это чтобы avva знал, что я догадался, а остальные могли подумать.

[qaraabayna.livejournal.com]

Для автора работающего в гугле, вопрос "что такое" является провокационным.

[pinkoflamingo.livejournal.com]

Результат сдвига зависит не от соответствующих битов аргумента.

[spamsink.livejournal.com]

Смотря как определить соответствие. Важно, что каждый бит сдвига на константу зависит ровно не более чем от одного бита сдвигаемого аргумента, а соответствие между битом аргумента и битом результата определяется размером сдвига.

[pinkoflamingo.livejournal.com]

Тогда непонятно, с чего вдруг "ровно не более чем от одного бита" — в задаче написано "значение которой в каждом бите результата зависит только от соответствующих битов аргументов".

[spamsink.livejournal.com]

Аргументов может быть два.

[pinkoflamingo.livejournal.com]

И?

[avva.livejournal.com]

Это я виноват, как обычно. Слишком строго определил, не подумав. Сдвиг тоже традиционно является битовой операцией, хотя под это определение не подпадает. Извините, сейчас исправлю.

[dimrub.livejournal.com]

Да, черт побери!

Все-таки три: вместо энд и инверсии используем функцию, которая является их комбинацией.

[spamsink.livejournal.com]

А, черт, надо было на Верилоге писать! :)

[softmaster.livejournal.com]

сорри, а что за битовая функция такая?

[dimrub.livejournal.com]

Я не знаю, как она называется, но могу нарисовать ее таблицу истинности. Требования ведь не было, чтобы у функции название было, правильно? :)

[avva.livejournal.com]

Это три, как тебе уже указали :-)

[pinkoflamingo.livejournal.com]

1. Последовательное приложение g(x) гоняет единички влево по слову, сохраняя их количество.

[avva.livejournal.com]

Не совсем.

[pinkoflamingo.livejournal.com]

Совсем.

[pinkoflamingo.livejournal.com]

OK, если внятно писать, то перебирает все слова с количеством единиц как в исходном слове, по возрастанию.

[qaraabayna.livejournal.com]

1. Округляет до большей степени двойки

[avva.livejournal.com]

Не совсем.

[qaraabayna.livejournal.com]

Забыл сказать - той степени для которой нужно округление

[dimrub.livejournal.com]

1. - не понял, в какой системе представления знака? Если 1's complement, то f == 0, h == Id, g == h == Id
2. если бы не цифры, хватило бы одной. Будем думать, что делать с цифрами (видимо, надо придумать такой f и f^-1, чтобы посредине можно было сделать or с соотв. маской).

[faceted-jacinth.livejournal.com]

лол
f == "самый младший ненулевой разряд", вообще-то.

[avva.livejournal.com]

1. 2's complement, как весь мир давно :-)

[pilpilon.livejournal.com]

1.берет самую младшеразрядную группу единиц. старшую сдвигает влево, остальные до упора вправо.
2. за две операции:
(((X xor A) and B) xor A)
где А - учетверенный пробел, В -его обращение.

[avva.livejournal.com]

1. Верно. А зачем это нужно?
2. нет, это что-то не то

[pilpilon.livejournal.com]

дя перебора всех чисел с данным числом единиц?

2.да, у меня странная была идея что это можно сделать без сдвигов, какой-то бред написал.
можно :
С = 01000000010000000100000001000000
F(X): X & C
G(X) : ~(X >>1)
H(X) : X & F(G(X))

[pilpilon.livejournal.com]

чего-то я странное написал

[neatfires.livejournal.com]

1. счеты? :)

[avva.livejournal.com]

В каком-то смысле, да :-)

[neatfires.livejournal.com]

Может, state machine для перебора всех вариантов расстановки определенного количества единиц и нулей (начиная с заданного state)? Если начать с x=00000111 и последовательно печатать g(x), g(g(x)), g(g(g(x))) итд., пока не упремся в 11100000, то функция переберет все варианты.

[neatfires.livejournal.com]

ОК. Запишите мне это в счет будущего (жаль, нескоро) интервью :Р

[qehgt.livejournal.com]

>(update: первоначально я забыл разрешить b) выше, виноват)
А я уже решил, что совсем квалификацию потерял. С этим пунктом в 3 "операции" всё укладывается, конечно же.

[avva.livejournal.com]

Ага. Извините :)

[avva.livejournal.com]

Что-то не то. Например, h(x) у вас вычислено неправильно, а h(x) ^ x уже правильно, хотя должно было дать неверный результат из-за ошибки в h(x) :)

И непонятно, зачем нужна такая g(x).,

[avva.livejournal.com]

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) вместо своего неправильного :) (и да, у нее есть более полезное применение).

[avva.livejournal.com]

:)

[avva.livejournal.com]

не совсем.

[qaraabayna.livejournal.com]

Сырого материала слишком много, чтобы задачка была интересной

1ая задача

[baramin.livejournal.com]

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 :)

Re: 1ая задача

[baramin.livejournal.com]

Возрастающий шейкер для 1 и 0?

Re: 1ая задача

[avva.livejournal.com]

:)

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

[master-nemo.livejournal.com]

только четыре:
x:= x and not ((x shr 1) and c);
не знаю я как AND NOT записать в 1 функцию
я помню как надо мной смеялись когда я такую фигню с флагами в WINAPI проделывал, но ведь работало!
А если есть какой безумный способ преобразовать все к 3м операциям через эквивалентные преобразования то я этим извращением сейчас заниматься не буду :)

upd fix

[master-nemo.livejournal.com]

где С:={8 пробелов}