Calculation of maximum power 2, which evenly divides the number in C

Question

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

IE:
Login → Logout

4 (0100) -> 4 8 (1000) -> 8 12 (1100) -> 4 14 (1110) -> 2 24 (11000) -> 8 etc.... 

It seems that there is some bitwise logic that might work: if you look at the input in binary format, the rightmost bit is the solution. How to determine this value in C? Is there any other solution that could be simpler?

Thanksgiving and Jonathan

Answer 1

If you are ready to accept 2-dimensional arithmetic:

x & -x

If you do so much (or even just become interested), find yourself a copy of Hacker Delight.

edit: avakar correctly notes that this is independent of 2 additions if the type is not specified. The relevant section of the standard is §6.2.5, clause 9:

A calculation involving unsigned operands can never be overflowed, since a result that cannot be represented by an unsigned integer type is equal to a reduced modulus number, which is one greater than the largest value that a result type can represent.

"one is greater than the largest value" leaves some room for maneuver for a particularly perverse implementation (in particular, an implementation that does not use a binary file, for example), but you are unlikely to come across this.

Answer 2

Without using floating point arithmetic:

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

Simplification and edge cases remain as exercises for the reader.

Answer 3

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

 x & (~x+1) 

The low bit level that you absolutely must know gives a detailed explanation.

Answer 4

A number in the form 2 ^ n is written in binary form by 1 with a sequence of 0 or more than 0. For example, 1, 10, 100, 1000, ... etc. All have a power of 2.

To get a maximum power of 2 dividing a given number, you can follow these two steps:

• Enter the number in binary form. For example, if the number is 168, write 10101000.

• Delete all the bits before the first bit on the right side that contains 1. In case of 168, the remaining 1000 (= 8 in decimal) after deleting the first part of 10101000.

Your result remains - that is, the maximum power of 2 dividing the number.

Programmatically, let x be your input number. Then your desired result would be: x - (x ^ (x-1))

Explanation:

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

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