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

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开发者_如何学Python^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

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.

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

x & (~x+1) 

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

Without using floating point arithmetic:

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

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

A number in the form 2^n is written in binary by a 1 followed by a series of 0 or more 0s. For example, 1, 10, 100, 1000, ... etc. are all power of 2.

To get the highest power of 2 that divides a given number, you can do the following two steps:

1. Write the number in binary form. For example, if the number is 168, write 10101000.

2. Strike off all the bits before the first bit from right hand side that contains 1. In the case of 168, what remains is 1000 (= 8 in decimal) after striking off first part of 10101000.

What remains is your result - that is, highest power of 2 that divides the number.

Programmatically, let x is your input number. Then your desired output will be: x - (x ^ (x-1))

Explanation:

x ^ (x-1) [meaning x XOR x-1] gets rid of the first 1 from LSB (least significant bit) side

x - (x ^ (x-1)) gets rid of the remaining part, and retains only first 1 from LSB side.