Determining if an integer is a power of 2 — part 2

Author:	Wojciech Muła
Added on:	2014-10-01

The idea is simple:

0. precondition: x is not zero;
1. isolate lowest bit set: x & -x;
2. check if this number is equal to x: x == (x & -x).

Sample code:

uint32_t isolate_lowest_set(uint32_t x) {
    return x & -x;
}

int is_power_of_two_non_zero(uint32_t x) {
    return isolate_lowest_set(x) == x;
}

int is_power_of_two(uint32_t x) {
    return x != 0 && is_power_of_two_non_zero(x);
}

GCC 4.8.2 generates for is_power_of_two following code:

8b 54 24 04     mov    0x4(%esp),%edx
31 c0           xor    %eax,%eax
85 d2           test   %edx,%edx
74 0e           je     8048488 <is_power_of_two+0x18>
89 d0           mov    %edx,%eax
f7 d8           neg    %eax
21 d0           and    %edx,%eax
39 c2           cmp    %eax,%edx
0f 94 c0        sete   %al
0f b6 c0        movzbl %al,%eax
f3 c3           repz ret

Unfortunately compiler inserted a jump. But when we are sure that arguments are non-zero then only 5 basic instruction are required to perform this check.