Завершающие нули - C

Шестнадцатеричные константы объединяются по И со значением, чтобы проверить, является ли последнее [число] цифр нулем. 0x0000FFFF — это число с 16 единицами в двоичном формате. Если значение, объединенное по И с 0x0000FFFF, равно 0, вы знаете, что последние 16 цифр являются нулями (проверка ifs на обратную сторону этого утверждения). Идем дальше 0x000000FF — это число с 8 единицами в двоичном виде. Следующая проверка предназначена для последних 8 цифр, следующая для 4 цифр и последняя для 2 цифр, поскольку 0x00000003 равно 11 в двоичном формате. После проверки числа сдвигаются, чтобы проверить, равны ли нулю и последующие цифры. Таким образом, мы можем проверить любое количество завершающих нулей, поскольку значения являются степенью двойки, и их добавление работает точно так же, как работа с двоичным кодом.

Последний оператор проверяет последнюю цифру после выполнения всех предыдущих сдвигов - И с 1 и проверяет, является ли это 0 или 1 с помощью XOR (^).

Эта программа проверяет числа с 32 битами. Вы можете изменить первый if на while, чтобы проверить больше, например. 64-бит, числа. Другой способ — проверить с помощью 0xFFFFFFFF, а затем сдвинуть сразу 32 бита.

Строка n += (x & 1) ^ 1 проверяет младший значащий бит (LSB) текущего состояния x. Если младший бит равен 1, то (x & 1) дает 1, которая затем подвергается операции XOR (символ вставки '^' означает XOR двух значений) с 1, чтобы получить 0 (1 ^ 1 == 0). Когда x имеет 0 в LSB и XOR с 1, это дает 1 (0 ^ 1 == 1).

!(x&0x0000FFFF) будет истинным только тогда, когда последние 16 бит x будут равны 0. & — это побитовое И, а 0x0000FFFFF — это число, оканчивающееся на 16 единиц. Таким образом, результат операции and равен 0, если и только если все 16 завершающих битов равны 0 (и, таким образом, FALSE и 1 меняют значение истинности), потому что если среди последних 16 есть хотя бы одна 1, то и с соответствующей 1 в константе будет 1. Тогда и не равно 0 (поэтому ИСТИНА и ! меняют местами значение истинности).

Таким образом, код говорит: если последние 16 бит равны 1, добавьте 16 к n и отбросьте последние 16 бит (это то, что делает x >>= 16).
Следующая строка говорит аналогичным образом: если последние 8 битов (возможно, сокращенное x) равно 0, добавьте 8 к n и отбросьте крайние правые 8 бит, и так далее для 4 и 2 бит

Последняя строка добавляет 1, если самый правый бит (x&1) равен 0, иначе 0 (1^1 = 0).

Итак, скажем, если крайние правые 15 битов равны 0, первое if будет ложным, n останется равным 0.
Второе будет истинным, так как у нас их больше 8. Новый x будет иметь 7 нулевых битов, и n= 8.
Третье тоже будет верным (у нас осталось 4 или больше), поэтому новый x имеет 3 нулевых бита после сдвига и n=12.
Четвертое тоже будет верным (2 или больше 0), так что новый x имеет 1 0-бит и n=14.
Последний оператор добавляет 1, поэтому получаем n=15.

Поскольку мы используем убывающие степени числа 2, нам не нужен цикл. Таким образом мы получаем все возможные значения n (кроме 32, для входа x=0, полностью правильная функция должна проверять это и досрочно прерывать работу.

n += (x & 1) ^ 1; // anyway what does this do ?

Это проверяет самый правый бит. Либо он установлен, либо НЕ установлен.

Если он установлен, то НЕТ другого 0 для добавления к промежуточной сумме завершающих нулей, поэтому n+=0.

Если он НЕ установлен, то к промежуточной сумме завершающих нулей нужно добавить еще один 0, поэтому n+=1.

Кроме того, ваш пример НЕ компилируется, в нем отсутствуют два ; следующим образом:

unsigned tzr(unsigned x)
{
    unsigned n; /* number of bits */

    n = 0;
    if (!(x & 0x0000FFFF)) { n += 16; x >>= 16; }
    if (!(x & 0x000000FF)) { n += 8; x >>= 8; }
    if (!(x & 0x0000000F)) { n += 4; x >>= 4 } // won't compile due to missing ;
    if (!(x & 0x00000003)) { n += 2; x >>= 2 } // won't compile due to missing ;

    n += (x & 1) ^ 1; // anyway what does this do ?

    return n;
}

Кроме того, вы всегда можете попробовать распечатать данные, например, каждая степень числа 2 имеет несколько конечных нулей, но только нечетное количество конечных нулей увеличивается на дополнительную 1 из n += (x & 1) ^ 1;...

cout << tzr(9) << endl << endl; // 1001 (not a power of two )
cout << tzr(8) << endl << endl; // 1000 (8>>2 & 1)^1==1
cout << tzr(4) << endl << endl; // 0100 (4>>2 & 1)^1==0
cout << tzr(2) << endl << endl; // 0010 (   2 & 1)^1==1
cout << tzr(1) << endl << endl; // 0001 (   1 & 1)^1==0

tzr(9) == 0 ==> 0 + (9 и 1) ^ 1 == 0 + 0

tzr(8) == 3 ==> 2 + (8>>2 & 1) ^ 1 == 2 + 1

tzr(4) == 2 ==> 2 + (4>>2 и 1) ^ 1 == 2 + 0

tzr(2) == 1 ==> 0 + (2 и 1) ^ 1 == 0 + 1

tzr(1) == 0 ==> 0 + (1 и 1) ^ 1 == 0 + 0

Программа завершилась с кодом выхода: 0

Вы говорите: «Мне нужна программа, которая возвращает количество конечных нулей в двоичном представлении числа». Но обязательно ли это должна быть программа, которую вы нашли? Вот альтернативное решение, которое реализует tzr() ровно в одной строке кода:

#include <stdio.h>
#include <stdlib.h>

int tzr(int n) { /* --- every time n is even, add 1 and check n/2 --- */
  return ( (n/2)*2 == n? 1+tzr(n/2) : 0 ); }

int main ( int argc, char *argv[] ) { /* --- test driver --- */
  int n = (argc>1? atoi(argv[1]) : 1000);
  printf("tzr(%d) = %d\n", n,tzr(n)); }

Так легче понять?

(P.S. Вы можете использовать битовые маски и сдвиги вместо моих делений и умножений. Это может быть немного эффективнее, но я подумал, что мой способ может быть немного более простым для чтения.)