Calculating Highest Power of 2 That Evenly Divides a Number in C

Question

I need to write some logic to determine, given an even number, the highest power of two that evenly divides it. What is the maximum value of 2^n where Input % 2^n == 0?

IE:
Input -> Output

4 (0100) -> 4

8 (1000) -> 8

12 (1100) -> 4

14 (1110) -> 2

24 (11000) -> 8

etc....

It looks like there be some bitwise logic that may work out: when looking at the input in binary, the rightmost one bit appears to be solution. How do I determine this value in C? Is there another solution that may be easier?

Thanks- Jonathan

Answer 1

Without using floating point arithmetic:

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

Simplification and edge cases are left as exercises for the reader.

Answer 2

If you are willing to assume 2's complement arithmetic:

x & -x

If you do a lot of this sort of thing (or even if you just find it interesting), find yourself a copy of the book "Hacker's Delight".

edit: avakar correctly notes that this doesn't depend on 2's complement if the type is unsigned. The relevant section of the standard is §6.2.5, paragraph 9:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

"one greater than the largest value" leaves some wiggle room for an especially perverse implementation (in particular, an implementation that doesn't use binary, for example), but you're pretty unlikely to encounter that.

Answer 3

We can replace (-x) by (~x + 1):

x & (~x+1)

Low Level Bit Hacks You Absolutely Must Know provides detailed explanation.