How to find the largest power of two divisor of a given integer?

Question

Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero.

When $x$ is zero, the algorithm should return zero. For odd numbers, it should return one, since the largest power of two that divides these numbers is $2^0$.

How to write an algorithm for this? (any programming language would do, or pseudocode)

Answer 1

After reading through your question carefully, it is clear that this is not actually the Find First Set-operation as others have answered as Find First Set would give you the largest value $n$ for which $p = 2^n$ is a factor of your number, whereas what you where asking for was the corresponding $p$.

This is good as the final step from your question to FFS is the most complicated part.

Assuming that your numbers are in a normal two's-complement encoding, the result should be a number with the same trailing zeroes and lowest one bit (if present) as $x$ and the remaining bits set to zero.

Using a few bit-twiddling hacks we can find the result in just a few steps:

• Take the bitwise inverse of $x$ to get a number that has all bits set differently.
• Add one to the inverse to restore only the trailing zeroes and the lowest one.
• Take the bitwise and between this value and the original number to set all bits not affected by the previous step to zero.

As these are very simple instructions they should exist in pretty much any language you can think of, and they usually look the same.

For example this is how it looks in C, C++, Python, Java, and Javascript: p = x & (~x + 1)

If anyone has an example of a language where it looks different, please add a comment.

Edit:
A simplification that was previously overlooked is using that -x in two's complement is defined as ~x + 1 giving the even shorter code of p = x & -x.

Answer 2

You just need to count the number of $0$ at the end of the binary encoding of $x$.

Answer 3

Your operation is known as find last set, count trailing zeroes, bit scan forward, and possibly other names. Many modern CPUs support it natively. On Wikipedia you can find several fast implementations.

Answer 4

This really depends on your computing platform and how your integer is represented (and how big it might be). If we're talking about an integer which fits into a single register of your real-world computer, then as @YuvalFilmus writes, there are often assembly language instructions like "find first set" or "count trailing zeros" which perform this computation directly. If you're using a compiler like GCC or clang, and a C-like/C-friendly language, you can use these via a compiler builtin, e.g. __builtin_ffs()/__builtin_ffsl() etc. See:

• GCC builtins documentation
• clang builtins documentation

for their exact semantics.

However, if your integer is of arbitrary length, things are different... if it's still in binary representation, then - you're essentially looking for the first non-zero byte or word; and within that word you're back to the previous case. This takes $O(n)$ operations, naturally.

If the representation is available more opaquely (e.g. you are only allowed to perform arithmetic operations on it, as in the Blum-Shub-Smale model) then again things are different - and perhaps slightly more interesting: You could then try a binary search for the power $n$ of the greatest power-of-two divisor. That should take $O\!\left(\log(n)\right)$ operations.

On the other hand, if the representation is in a non-power-of-2 basis, you might be in a bit of a bind, and I'm pretty certain it would be an $\Omega(n)$ algorithm. A straightforward thing to do would be changing the base of $x$ to base 2 (and I'm not sure you can do much better).