Может кто-нибудь объяснить эту функцию побитовое вычислить журнал (п)

Question

int howManyBits(int x) { 
    int concatenate; 
    int bias; 
    int sign = x >> 31; //get the sign 
    x = (sign & (~x)) | (~sign & x); 
    concatenate = (!!(x >> 16)) << 4; 
    concatenate |= (!!(x >> (concatenate + 8))) << 3; 
    concatenate |= (!!(x >> (concatenate + 4))) << 2; 
    concatenate |= (!!(x >> (concatenate + 2))) << 1; 
    concatenate |= x >> (concatenate + 1); 
    bias = !(x^0); 
    return concatenate + 2 + (~bias + 1); 

} 

Этот код представлен как способ вычислить минимальное количество битов, требуемых для представления целого числа n в дополнение до 2, в предположении, что тип int данных представлен 32 битами. Правое смещение считается арифметическим.

Я понимаю, что базовый метод состоит в том, чтобы взять лог-базу 2 из n, округлить ее, а затем добавить 1 бит для учета знакового бита.

Я также понимаю, что левый сдвиг эквивалентен умножению на 2 и сдвига вправо эквивалентен делению на 2.

, как говорится, без комментариев, которые я не могу расшифровать, что этот код делает дальше участок, где он получает значение знакового бита. Я работал над ним на карандаше и бумаге с образцом int значения 5 - код работает, но я не понимаю, почему.

Может ли кто-нибудь дать интуитивное описание того, что делает код?

Answer 1

Этот код может содержать некоторые комментарии.

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

x = (sign & (~x)) | (~sign & x); 

Я думаю, что следующее было бы более понятно:

x = sign ? ~x : x; 

Далее идет поиск наивысший 1 бит сделано с двоичным поиском. Сначала выполняется поиск верхней половины слова.

concatenate = (!!(x >> 16)) << 4; 

Если верхняя часть имеет 1, то результат 16. 16 используется в дальнейшем как в качестве части ответа, но и определить, где искать дальше. Поскольку он используется в смещениях, которые следуют за ним, это приведет к следующим испытаниям либо с верхней половиной платы, либо с нижней половиной.

Следующие операции конкатенации выполняются в постепенно уменьшенном фрагменте исходного номера, который является самым значительным в верхних 8 битах или младших 8 битах из 16 бит, которые были выбраны, затем верхние 4 бита или более низкие 4 бита из 8 бит, которые были выбраны, и так далее.

concatenate |= (!!(x >> (concatenate + 8))) << 3; // Check which 8 bits 
concatenate |= (!!(x >> (concatenate + 4))) << 2; // Check which 4 bits 
concatenate |= (!!(x >> (concatenate + 2))) << 1; // Check which 2 bits 
concatenate |= x >> (concatenate + 1);   // Check which 1 bit 

Уклонение - это просто проверка числа 0 или нет. Это 1, только если x равно 0. Я не понимаю необходимости в XOR-операторе.

И, наконец, части прилагаются вместе.