Problem

For a provided non-negative integer number n we need to check if this number is a power of two. A positive integer number n is a power of 2 if it could be represented as n = 2 ^ m, where m is some non-negative integer number.

Examples:

Solution

fn power_of_2(n: u32) -> bool {
    (n != 0) && (n & n - 1 == 0)
}

Explanation

The first naive solution for this puzzle that would often come to mind is just to divide the number n by 2 until it becomes 1 and see if at some point the remainder of the division is not 0 - in that case n is not the power of 2:

  fn power_of_2(mut n: u32) -> bool {    
    if n == 0 {
        return false;
    }

    while n > 1 {
        if n % 2 != 0 {
            return false;
        }
        n = n / 2
    }
    return true;
}

The naive solution would have the logarithmic complexity O(log n). That is not bad but we could do much better just using the magic of numbers and bitwise operations.

The actual solution is based on the observation that the power of 2 numbers n in binary form look like that (n = 1, 2, 4, 8, 16...): 1, 10, 100, 1000, 10000.... In other words, they always have a leftmost 1 and then all zeros to the right. And if we substruct n - 1 from these numbers (n - 1 = 0, 1, 3, 7, 15...), we would get in binary form: 0, 1, 11, 111, 1111.... In other words, the binary numbers would always (except for 0) have all 1s. It means that if we apply the bitwise AND operation to both of these numbers (n & n - 1) we should always get 0 as a result (the numbers would neutralize each other). Also, we process n != 0 specifically, because 0 could not be a power of 2 anyway.

Complexity

The time complexity of the solution is constant O(1) (where n is the number we check for being a power of 2).

---

Rust Playground with this code