How to check whether a value is power of two in Go?

In this article, I’m explaining how to check whether a value is power of two in Go.

What value is a power of two?

A power of two is a number that can be expressed as 2 raised to some non-negative integer exponent. In other words, a value is a power of two if it can be written in the form of 2^k, where k is a non-negative integer.

Power of two values are obtained by repeatedly multiplying 2 by itself. Here are the first few power of two values:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
...

Following code is one of the example codes for checking whether a value is power of two in Go.

func isPowerOfTwo(n int) bool {
    if n<=0{
        return false 
    }  
    if n==1{
        return true
    }
    if n%2==1{
        return false
    }
    n = n/2
    res := isPowerOfTwo(n)
    return res
}

Explanation

The given code is a recursive function called isPowerOfTwo that checks whether a given number n is a power of two. Let’s go through the code step by step:

1. 1. The function isPowerOfTwo takes an integer n as a parameter and returns a boolean value indicating whether n is a power of two.

1. 1. The first condition checks if n is less than or equal to zero (n<=0). If it is, the function immediately returns false. This is because zero and negative numbers cannot be powers of two.

1. 1. The second condition checks if n is equal to 1 (n==1). If it is, the function returns true. This is because 1 is considered a power of two (2^0 = 1).

1. 1. The third condition checks if n is odd (n%2==1). If n is odd, it means it cannot be a power of two since powers of two are always even. In this case, the function returns false.

1. 1. If none of the above conditions are met, it means n is even and greater than 1. In this case, the function divides n by 2 (n = n/2) and assigns the result back to n.

1. 1. The function then recursively calls itself with the updated value of n, i.e., isPowerOfTwo(n).

1. 1. Finally, the result of the recursive call is stored in a variable called res. The function returns the value of res, which indicates whether n is a power of two.

By continuously dividing n by 2 and checking for odd numbers, the function recursively checks whether n can be reduced to 1. If it can, it means the original input n was a power of two. If it cannot be reduced to 1 or if it encounters zero or negative numbers, it means n is not a power of two.

Another way

The following code is given from 「Golang Program to check whether given positive number is power of 2 or not, without using any branching or loop」

package main

import (
   "fmt"
   "strconv"
)

func CheckNumberPowerOfTwo(n int) int {
   return n & (n-1)
}

func main(){
   var n = 16
   fmt.Printf("Binary of %d is: %s.\n", n, strconv.FormatInt(int64(n), 2))
   flag := CheckNumberPowerOfTwo(n)
   if flag == 0{
      fmt.Printf("Given %d number is the power of 2.\n", n)
   } else {
      fmt.Printf("Given %d number is not the power of 2.\n", n)
   }
}

Output will be like this.

Binary of 16 is: 10000.
Given 16 number is the power of 2.

Explanation

The given code defines a function called CheckNumberPowerOfTwo that takes an integer n as input and returns an integer result. Let’s break down the code step by step:

1. 1. The code uses a bitwise operation called the “bitwise AND” (&) operator to perform the operation n & (n-1).

1. 1. The expression (n-1) subtracts 1 from the value of n.

1. 1. The bitwise AND operation (&) performs a bitwise comparison between the binary representations of n and (n-1). It compares each corresponding pair of bits and returns a new number where each bit is set to 1 only if both corresponding bits in n and (n-1) are 1. Otherwise, the bit is set to 0.

1. 1. The result of the bitwise AND operation is returned by the function.

Now, let’s understand the purpose of this code and how it determines whether a given number n is a power of two:

• • If n is a power of two, it will have exactly one bit set to 1 in its binary representation (e.g., 2 = 10, 4 = 100, 8 = 1000, etc.).

• • When we subtract 1 from a power of two, we get a number that has all the bits to the right of the original bit set to 1 and the original bit set to 0 (e.g., 1 = 1, 3 = 11, 7 = 111, etc.).

• • When we perform a bitwise AND operation between n and (n-1), the result will be 0 if n is a power of two. This is because all the bits of (n-1) to the right of the original bit in n will be set to 1, and the original bit in n will be set to 0. Since all the bits are different, the bitwise AND operation will result in 0.

• • However, if n is not a power of two, it will have more than one bit set to 1 in its binary representation. In this case, the bitwise AND operation between n and (n-1) will produce a number that is not equal to 0.

Therefore, the code return n & (n-1) effectively checks whether n is a power of two. If the result is 0, it means n is a power of two. Otherwise, it is not a power of two.