?

Log in

No account? Create an account
задачки про биты (для программистов) - Поклонник деепричастий [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: pinkoflamingo
2008-01-12 03:13 am
1. Последовательное приложение g(x) гоняет единички влево по слову, сохраняя их количество.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 10:20 am
Не совсем.
(Ответить) (Parent) (Thread) (Развернуть)
From: qaraabayna
2008-01-12 03:46 am
1. Округляет до большей степени двойки
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 10:20 am
Не совсем.
(Ответить) (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: 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: neatfires
2008-01-12 11:35 am
1. счеты? :)
(Ответить) (Thread)
[User Picture]From: avva
2008-01-12 11:49 am
В каком-то смысле, да :-)
(Ответить) (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)
(Удалённый комментарий)
(Удалённый комментарий)
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: 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)