Удаление первого бита

Question

Есть ли эффективный способ удалить первый бит числа в C++/Python, если вы не знаете, насколько велика цифра или ее тип данных?

Я знаю в Python. Я могу это сделать, получив bin (n), обрезая строку на 1, а затем переработав ее в int, но мне любопытно, есть ли более «математический» способ сделать это ,

например. говорят, что число равно 6, что равно 110 в двоичном формате. Нарезать первый бит и становится 10, или 2.

Answer 1

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

def upper_bit(x): 
    while x & (x - 1): 
     x &= x - 1 
    return x 

Теперь вы можете использовать его в качестве маски:

def mask_off(x, mask): 
    return x & ~mask 

>>> mask_off(6, upper_bit(6)) 
2 

Обратите внимание, что это только работает для положительных чисел, из-за безграничной природы Python ints.

Answer 2

смотрит на 110 (6) десятичного

Наиболее значимые бит 100 (4 десятичных) // - Обратите внимание, что это всегда сила 2

Создать маску: один меньше, чем старший бит равен 011 (3 десятичных)

Маскирования старшего бита, используя побитовый и: 110 & 011 = 10 (2 десятичного)

Вычисляя MSB (старший бит) было обработано здесь и в других местах довольно часто

Answer 3

Ну, вы могли бы создать цикл, в котором вы бы удвоить некоторую переменную (скажем, х) в каждой итерации, а затем проверить, является ли эта переменная больше вашего. Если это так, разделите его на два и вычтите из своего номера. Например, если ваш номер 11:

-первая итерация: х = 1 < 11, поэтому продолжают

-Второй итерация: х = 2 < 11, поэтому продолжают

-third итерация: х = 4 < 11, так что по-прежнему

-fourth итерации: х = 8 < 11, так что по-прежнему

: итерация пятой х = 16> 11, таким образом разделить на два х: х = 8. Затем вычтите 8 из своего номера и получите ответ:

11-8 = 3.

Answer 4

В Python, я бы один из них:

def chop_msb(i): 
    return i >> 1 & i 
print chop_msb(6) 
> 2 
print chop_msb(12) 
> 4 
print chop_msb(32) 
> 0 

def chop_msb2(i): 
    return 2**(i.bit_length()-1)^i 

print chop_msb2(6) 
> 2 
print chop_msb2(12) 
> 4 
print chop_msb2(32) 
> 0 

Объяснение:

• Первое:

Это в значительной степени делает то же самое, как @ решение Гленна, но он более эффективно вычисляет маску.

• Второе:

Это операцию XOR старший бит i с i. Вычисление MSB выполняется (в этом случае) путем вычисления 2 в (длина бит i-1).

XOR возвращает все биты, которые установлены либо в первом значении, либо во втором значении, но не в обоих. Это означает, что вы в основном установить MSB 0 в этом случае:

6: 110 XOR 100 = 010 = 2 
12: 1100 XOR 1000 = 0100 = 4 
32: 100000 XOR 100000 = 000000 = 0 

Answer 5

Если вы используете компилятор, который поддерживает __builtin_clz, и вы ограничиваете себя к типу, который __builtin_clz поддерживает, вы можете сделать:

unsigned int chopWithBuiltin(unsigned int x) { 
    //get number of leading redundant sign bits, 
    //which is one less than the position of the MSB 
    int msb_idx = __builtin_clz(x); 
    //now make a mask that is all the bits below the MSB 
    int mask = UINT_MAX >> (msb_idx+1); 
    return x & mask; 
} 

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

Для отрицательных чисел вы можете построить что-то похожее с __builtin_clrsb, но это усложняется.