Замыкающие нули - C

Question

Мне нужна программа, которая возвращает число конечных нулей в двоичном представлении числа. Я нашел в Интернете функцию, написанную на C, но я не понимаю, как она работает

Это функция:

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; }
    if (!(x & 0x00000003)) { n +=  2; x >>=  2; }

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

    return n;
}

Теперь я действительно пытался понять, как это работает, но я не понимаю. Мне действительно нужен кто-то, кто мог бы объяснить это мне, я нахожу этот код очень сложным.

И о тех шестнадцатеричных констант, это их значения:

0x0000FFFF = 65535
0x000000FF = 255
0x0000000F = 15
0x00000003 = 3

Теперь, почему программа использует эти значения и делает побитовое И с числом?

Тогда я знаю, что если вы хотите обрабатывать большие числа, вы должны
использовать while вместо первого if утверждение, как это:

while (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; } // why should I need this ?

Но я не знаю почему! Какая разница в использовании while вместо if в этом случае?

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

!(x&0x0000FFFF) будет верно только тогда, когда последние 16 бит x все 0. & поразрядно и, и 0x0000FFFFF число, заканчивающееся на 16 1. Таким образом, результат и равен 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 0 битов, а n=8.
Третий также будет верным (у нас еще 4 или более), поэтому новый x имеет 3 0 битов после сдвига и n=12.
Четвертый также будет истинным (2 или более 0), поэтому новый x имеет 1 0-битный и n=14.
В заключительном утверждении добавляется 1, поэтому получаем n=15.

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

Answer 5

Вы говорите: "Мне нужна программа, которая возвращает число конечных нулей в двоичном представлении числа". Но это должна быть программа, которую вы нашли? Вот альтернативное решение, которое реализует 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)); }

Это легче понять?

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