Каморка

Подскажите, please, что бы это значило:

Let n be a 32 bit word. Expression if (! (n&=(n-1))) determines if:

1. the most significant nibble of the word contains n set bits
2. n is a power of 2
3. n is a positive integer

Вопрос из теста при приеме на работу.
Спасибо.

тест на понимание двоичного представления чисел и побитовых операций.

правильный ответ, по-моему - 2.

Lilia писал(а):Подскажите, please, что бы это значило:

Let n be a 32 bit word. Expression if (! (n&=(n-1))) determines if:

1. the most significant nibble of the word contains n set bits
2. n is a power of 2
3. n is a positive integer

Вопрос из теста при приеме на работу.
Спасибо.

http://youtube.com/watch?v=91IBfCjuDYY

Ranger писал(а):тест на понимание двоичного представления чисел и побитовых операций.
правильный ответ, по-моему - 2.

обоснуй (с)

Если n & (n-1) дает 0, то в общем-то логично, что n есть степень 2.
типа 00000100 & 00000011 = 00000000

accnt5 писал(а):Если n & (n-1) дает 0, то в общем-то логично, что n есть степень 2.
типа 00000100 & 00000011 = 00000000

а если n = 0101011111100011?

Stanislav писал(а):а если n = 0101011111100011?

Тогда n & (n-1) не даст 0.

наверное 1)

ffffffff == ffffffff & (fffffffe - 1)
ffffffe - 1 = ffffffff

если результат не нулевой, то будет положительным. Об отрицательном нужны дополнительные договоренности о представлении, а в условии говорится 32 WORD.

0001 & 0000 = 0000
0010 & 0001 = 0000
0011 & 0010 = 0010 = 2
0100 & 0011 = 0100 = 4
0101 & 0100 = 0100 = 4
0110 & 0101 = 0100 = 4
0111 & 0110 = 0110 = 6 -> не является степенью 2
1000 & 0111 = 1000 = 8
1001 & 1000 = 1000 = 8
1010 & 1001 = 1000 = 8
1011 & 1010 = 1000 = 8
1100 & 1011 = 1000 = 8
1101 & 1100 = 1100 = 12 - не является степенью 2
1110 & 1101 = 1100 = 12
1111 & 1110 = 1110 = 14 - не является степенью 2
..... дальше индукция.

[quote="meser"]если результат не нулевой, то будет положительным. Об отрицательном нужны дополнительные договоренности о представлении, а в условии говорится 32 WORD.

......
0100 & 0011 = 0100 = 4 -- неверно
......
1000 & 0111 = 1000 = 8 -- неверно

упс. старею
спасибо.

meser писал(а): 0110 & 0101 = 0100 = 4
0111 & 0110 = 0110 = 6 -> не является степенью 2
1000 & 0111 = 1000 = 8
1001 & 1000 = 1000 = 8
1010 & 1001 = 1000 = 8
1011 & 1010 = 1000 = 8
1100 & 1011 = 1000 = 8
1101 & 1100 = 1100 = 12 - не является степенью 2
1110 & 1101 = 1100 = 12
1111 & 1110 = 1110 = 14 - не является степенью 2
..... дальше индукция.

К чему это?
(!(n&=(n-1))) должно давать TRUE, n&=(n-1) должно давать FALSE, т.е. n&(n-1)=0. Это выполнимо только когда исходное n is a power of 2.
0010 & 0001 = 0, 0100 & 0011 = 0, 1000 & 0111 = 0 и т.д. Поправьте если что не так...

Вообще вопрос хитрый - n присваивается новое значение в процессе, так что правильнее наверное будет сказать, что правильный ответ #1, ибо как раз он выполним только при n=0
1. the most significant nibble of the word contains n set bits

Видно народ забыл как степень двойки в бинарном виде выглядит
Этот if как раз это и проверяет, а в n остаётся логарифм 2 от n.

да, про бинарный народ забыл - про шеснадцатиричный еще как-то помним. все-таки первое - ближе к телу.

п.с. про логарифмы не понял. log 2 n = ln n / ln 2 - равно нулю только при n=1. что здесь проверяется?