Какова функция log2 в бит-манипуляции?

Question

Почему мы используем log2, чтобы получить позицию самого правого установленного бита?Я не могу понятьВесь код здесь.Большое спасибо!

unsigned int getFirstSetBitPos(int n) 
{ 
    return log2(n & -n) + 1; 
} 

Answer 1

С двоичный логарифм в Википедии:

В математике двоичный логарифм (log ₂ n ) - это степень, на которую необходимо возвести число 2, чтобы получить значение n .То есть для любого действительного числа x ,

x = log ₂ ⁡ n ⟺ 2 ^x = n .

Например, двоичный логарифм 1 равен 0, двоичный логарифм 2 равен 1,двоичный логарифм 4 равен 2, а двоичный логарифм 32 равен 5.

Итак, в вашем коде n & -n сначала отключает все биты , кроме , самые правыебит, который был первоначально установлен в 1, затем требуется лог ₂ этого результирующего числа, чтобы получить его степень-2 (которая совпадает с позицией бита, основанной на 0,был установлен в 1), и, наконец, добавляет 1 к этому результату, чтобы получить битовую позицию на основе 1 (что странно, поскольку биты обычно обозначаются их позициями на основе 0).

Например, давайтепосмотрите на 5.В двоичном коде 5 - это биты 00000000000000000000000000000101 (предполагается, что 32-битный int тип), а -5 - это биты 11111111111111111111111111111011 (предполагается, что отрицательные целые числа реализованы с использованием 2s-дополнения ).Помните, что оператор & выполняет операцию по битам AND, которая возвращает 1 для данного бита, только если этот бит равен 1 в обоих входных числах,в противном случае возвращается 0.Таким образом:

  00000000000000000000000000000101 (5)
& 11111111111111111111111111111011 (-5)
----------------------------------
  00000000000000000000000000000001 (1)

Итак, 5 & -5 = 1, затем log2(1) = 0 и 0 + 1 = 1.

Давайте рассмотрим более сложное число, 1041204192, которое является битами00111110000011111000001111100000, а -1041204192 - биты 11000001111100000111110000100000:

  00111110000011111000001111100000 (1041204192)
& 11000001111100000111110000100000 (-1041204192)
----------------------------------
  00000000000000000000000000100000 (32)

Итак 1041204192 & -1041204192 = 32, затем log2(32) = 5 и 5 + 1 = 6.

Только для ударов, давайте посмотримв 0:

  00000000000000000000000000000000 (0)
& 00000000000000000000000000000000 (-0)
----------------------------------
  00000000000000000000000000000000 (0)

То есть 0 & -0 = 0, а log2(0) равно -INFINITY, что не определено для целых чисел.

Вот -1:

  11111111111111111111111111111111 (-1)
& 00000000000000000000000000000001 (--1)
----------------------------------
  00000000000000000000000000000001 (1)

Итак (-1) & -(-1) = 1, затем log2(1) = 0 и 0 + 1 = 1.

И -2:

  11111111111111111111111111111110 (-2)
& 00000000000000000000000000000010 (--2)
----------------------------------
  00000000000000000000000000000010 (2)

Итак (-2) & -(-2) = 2,затем log2(2) = 1 и 1 + 1 = 2.

И так далее ...