3
$\begingroup$

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)

$\endgroup$
2
  • 9
    $\begingroup$ Repeatedly divide $x$ by 2 until it becomes odd. $\endgroup$ Apr 5 at 12:14
  • $\begingroup$ This comment isn't intended as an answer (as it was already given), but rather as a way on how you can approach solving these kinds of issues. Ask yourself the same question about the largest power of 10 divisor, using a number written in base 10. What is the largest power of 10 divisor of 130,000? (it's 10,000) The exact same logic applies to finding the largest power of 2 divisor for an integer written in base 2. $\endgroup$
    – Flater
    Apr 7 at 9:44
10
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ x & (x-1) looks a little simpler. $\endgroup$
    – Pseudonym
    Apr 6 at 1:42
  • 2
    $\begingroup$ @Pseudonym That would also not be the right answer. Did you perhaps mean x & -x? Because I admit that I overlooked that one. $\endgroup$ Apr 6 at 1:52
  • 5
    $\begingroup$ Consider editing your answer to benefit from the comment thread and then you can flag the remainder of the comment thread to get it deleted. It would be a pity if the best available answer remained hidden in a comment. $\endgroup$ Apr 6 at 8:12
  • 1
    $\begingroup$ Rust has a function for this, trailing_zeros. There's also an x86 instruction for it, which Rust uses. $\endgroup$ Apr 6 at 16:29
  • 2
    $\begingroup$ @JohnDvorak That is the FFS-operation again, not the problem asked about. $\endgroup$ Apr 6 at 19:19
13
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think you mean last set. "Dividable by $2^n$" means n trailing zero bits. $\endgroup$
    – MSalters
    Apr 6 at 7:47
  • $\begingroup$ It depends on which direction you start looking. $\endgroup$ Apr 6 at 7:48
5
$\begingroup$

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:

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).

$\endgroup$
1
  • $\begingroup$ in Rust the compiler builtins are reachable as n.trailing_zeros() where n is a variable of a native integer type. $\endgroup$
    – cg909
    Apr 6 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.