gistfile1.md

A short proof why this works is this:

I assume the original version works (x & (x - 1)) == 0, barring zero. The change made is that we set the highest bit on the left hand side of the AND operator (by OR'ing with 0x8000000000000000).

We do not incorrectly recognize a previously recognized non-POT (power of two) as a POT. The reasoning is simple - we SET a bit before AND'ing, so the result can only increase (but not overflow). Since a previous nonzero result marked a non-POT, and the result could have only increased the stated is true.

The only other possible error is recognizing a a previous POT as a non-POT (not counting zero). When you look at POT's in binary they look like this:

00100000

If you substract one from them they look like this:

00011111

That is, the number gets filled with one's up to the position of the one in the POT. Since the highest POT starts with an one, this means that a POT - 1 always starts with a 0 bit. Thus setting the highest bit on the POT side of the AND has no consequences for the result of the AND, because the POT - 1 side always starts with a zero bit.

Zero is correctly marked as a non-POT, because ((0 | 0x8000000000000000) & (0 - 1)) == 0 is false.

Combine 1, 2 and 3 and QED.

One major problem: you are assuming data sizes of 64-bits. Its best to use fixed-size types to ensure portability in these cases (if the target system does not support the needed fixed-width size, it will most likely be emulated, guaranteeing correct behavior at a small performance cost.)

#include <stdint.h>
#include <limits.h>

uint64_t isPowerOf2u64(uint64_t x) {
    return `((x | UINT64_C(0x8000000000000000)) & (x - 1)) == 0`.
}

unsigned long isPowerOf2uLong(unsigned long x) {
    return `((x | (ULONG_MAX ^ (ULONG_MAX >> 1))) & (x - 1)) == 0`.
}

The isPowerOf2uLong will work for all long sizes, whether 32 bits, 64 bits, 128 bits, 40 bits, or any other crazy size.