Detecting Power of Two

by

Detecting whether a given number is a power of two using bit manipulation is an efficient technique that leverages the properties of binary representation. A number is a power of two if it has exactly one bit set in its binary representation. For example, 2 (binary 10), 4 (binary 100), and 8 (binary 1000) are all powers of two.

In binary, subtracting 1 from a power of two flips all the bits after the leftmost set bit (including the leftmost set bit). For a number that is a power of two, this operation results in a binary number where all bits that were zero become one, and the single one bit becomes zero. When you AND this number with the original number, you get 0. This property does not hold for numbers that are not powers of two.

Here’s how you can detect if a number is a power of two in Kotlin:

Kotlin
fun isPowerOfTwo(n: Int): Boolean {
    return n > 0 && (n and (n - 1)) == 0
}

fun main() {
    val numbers = listOf(1, 2, 3, 4, 5, 6, 7, 8, 16, 31, 32, 64, 1023, 1024)
    for (number in numbers) {
        println("$number is power of two: ${isPowerOfTwo(number)}")
    }
}

Explanation:

  • n > 0: First, we check if n is positive. Negative numbers and zero are not powers of two.
  • (n and (n - 1)) == 0: This is the key bit manipulation check. For a number that is a power of two, subtracting 1 will flip all the bits up to and including the first 1 bit from the right. The AND operation between the original number and this new value will be 0 if the number is a power of two. This happens because there’s only one 1 in the binary representation of a power of two, and subtracting 1 from it sets all bits to 0 up to the position of that 1. The AND operation with the original number (which has the 1 in that position and 0s elsewhere) results in 0.

This function efficiently checks if a number is a power of two with just a single AND operation and a comparison, making it highly efficient for use in performance-sensitive applications.

Leave a Comment