Вычисление наибольшей степени 2, которая равномерно делит число в C

Question

Мне нужно написать некоторую логику, чтобы определить, учитывая четное число. Высшая сила двух, которая равномерно делит ее. Какое максимальное значение 2 ^ n, где вход% 2 ^ n == 0?

IE:
Вход -> Выход

4  (0100)  -> 4

8  (1000)  -> 8

12 (1100)  -> 4

14 (1110)  -> 2

24 (11000) -> 8

etc....

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

Благодарения и Jonathan

Answer 1

Если вы готовы принять арифметику с дополнением 2:

x & -x

Если вы делаете много такого рода вещей (или даже если вам это просто интересно), найдите себе экземпляр книги "Восторг хакера".

edit: avakar правильно отмечает, что это не зависит от дополнения 2, если тип без знака. Соответствующий раздел стандарта - §6.2.5, параграф 9:

Вычисление без знака операнды никогда не могут переполняться, потому что результат, который не может быть представлен результирующий целочисленный тип без знака уменьшено по модулю число, которое является одним больше, чем наибольшее значение, может быть представлен в результате типа.

«на единицу больше, чем наибольшее значение» оставляет место для маневра для особенно извращенной реализации (в частности, для реализации, которая не использует двоичный код, например), но вы вряд ли столкнетесь с этим.

Answer 2

Без использования арифметики с плавающей точкой:

((x ^ (x - 1)) >> 1) + 1

Упрощение и крайние случаи оставлены в качестве упражнений для читателя.

Answer 3

Мы можем заменить (-x) на (~x + 1):

x & (~x+1) 

Низкоуровневые битовые хаки, которые вы должны знать предоставляет подробное объяснение.

Answer 4

Число в форме 2 ^ n записывается в двоичном виде 1, за которым следует серия 0 или более 0. Например, 1, 10, 100, 1000, ... и т. Д. Имеют степень 2.

Чтобы получить наибольшую степень 2, которая делит данное число, вы можете сделать следующие два шага:

1. Введите число в двоичном виде. Например, если число 168, напишите 10101000.

2. Вычеркнуть все биты перед первым битом с правой стороны, который содержит 1. В случае 168, после вычеркивания первой части 10101000 остается 1000 (= 8 в десятичном виде). ​​

То, что остается, - это ваш результат, то есть высшая степень 2, которая делит число.

Программно, пусть x - ваш номер ввода. Тогда ваш желаемый результат будет: x - (x ^ (x-1))

Пояснение:

x ^ (x-1) [означает x XOR x-1] избавляется от первого 1 со стороны младшего бита (младший бит)

x - (x ^ (x-1)) избавляется от оставшейся части и сохраняет только первую 1 со стороны LSB.