Given a huge integer number as a string, check if its a power of 2

Question

The number is huge (cannot fit in the bounds of unsigned long long int in C++). How do we check?

There is a solution given here but it doesn't make much sense. The solution here tries to repeatedly divide the large number (represented as a string) by 2 but I'm not sure I understand how the result is reached step by step. Can someone please explain this or propose a better solution? We cannot use any external libraries.

This is the sample code:

int isPowerOf2(char* str) 
{ 
    int len_str = strlen(str); 

    // sum stores the intermediate dividend while 
    // dividing. 
    int num = 0; 

    // if the input is "1" then return 0 
    // because 2^k = 1 where k >= 1 and here k = 0 
    if (len_str == 1 && str[len_str - 1] == '1') 
        return 0; 

    // Divide the number until it gets reduced to 1 
    // if we are successfully able to reduce the number 
    // to 1 it means input string is power of two if in  
    // between an odd number appears at the end it means  
    // string is not divisible by two hence not a power 
    // of 2. 
    while (len_str != 1 || str[len_str - 1] != '1') { 

        // if the last digit is odd then string is not 
        // divisible by 2 hence not a power of two  
        // return 0. 
        if ((str[len_str - 1] - '0') % 2 == 1) 
            return 0; 

        // divide the whole string by 2. i is used to 
        // track index in current number. j is used to 
        // track index for next iteration. 
        for (int i = 0, j = 0; i < len_str; i++) { 
            num = num * 10 + str[i] - '0'; 

            // if num < 2 then we have to take another digit 
            // to the right of A[i] to make it bigger than  
            // A[i]. E. g. 214 / 2 --> 107 
            if (num < 2) { 

                // if it's not the first index. E.g 214 
                // then we have to include 0. 
                if (i != 0)  
                    str[j++] = '0';                 

                // for eg. "124" we will not write 064 
                // so if it is the first index just ignore 
                continue; 
            } 

            str[j++] = (int)(num / 2) + '0'; 
            num = (num) - (num / 2) * 2; 
        } 

        str[j] = '\0'; 

        // After every division by 2 the  
        // length of string is changed. 
        len_str = j; 
    } 

    // if the string reaches to 1 then the str is 
    // a power of 2. 
    return 1; 
} 

I'm trying to understand the process in the while loop. I know there are comments but they arent really helping me glean through the logic.

Answer 1

This solution does work only for numbers which are not too large i.e. fits in the range of unsigned long long int. Simpler C++ solution using bitmanipulation for small numbers :-

int power(string s) {
    // convert number to unsigned long long int
    // datatype can be changed to long int, int as per the requirement
    // we can also use inbuilt function like stol() or stoll() for this
    unsigned long long int len = s.length();
    unsigned long long int num = s[0]-'0';
    for(unsigned long long int i = 1; i<len; i++) 
        num = (num*10)+(s[i]-'0');
    if(num == 1) 
        return 0;
    
    //The powers of 2 have only one set bit in their Binary representation
    //If we subtract 1 from a power of 2 what we get is 1s till the last unset bit and if we apply Bitwise AND operator we should get only zeros

    if((num & (num-1)) == 0) 
        return 1;
    return 0;
}

Answer 2

Let's start by figuring out how to halve a "string-number". We'll start with 128 as an example. You can halve each digit in turn (starting from the left), keeping in mind that an odd number affects the digit on the right^(a). So, for the 1 in 128, you halve that to get zero but, because it was odd, five should be kept in storage to be added to the digit on its right (once halved):

128
 v
028

Then halve the 2 as follows (adding back in that stored 5):

028
 v
018
 v
068

Because that wasn't odd, we don't store a 5 for the next digit so we halve the 8 as follows:

068
 v
064

You can also make things easier then by stripping off any leading zeros. From that, you can see that it correctly halves 128 to get 64.

To see if a number is a power of two, you simply keep halving it until you reach exactly 1. But, if at any point you end up with an odd number (something ending with a digit from {1, 3, 5, 7, 9}, provided it's not the single-digit 1), it is not a power of two.

By way of example, the following Python 3 code illustrates the concept:

import re, sys

# Halve a numeric string. The addition of five is done by
# Choosing the digit from a specific set (lower or upper
# digits).    

def half(s):
    halfS = ''                              # Construct half value.
    charSet = '01234'                       # Initially lower.
    for digit in s:                         # Digits left to right.
        if digit in '13579':                # Select upper for next if odd.
            nextCharSet = '56789'
        else:
            nextCharSet = '01234'           # Otherwise lower set.
        halfS += charSet[int(digit) // 2]   # Append half value.
        charSet = nextCharSet               # And prep for next digit.

    while halfS[0] == '0':                  # Remove leading zeros.
        halfS = halfS[1:]

    return halfS

# Checks for validity.

if len(sys.argv) != 2:
    print('Needs a single argument')
    sys.exit(1)

num = sys.argv[1]
if not re.match('[1-9][0-9]*', num):
    print('Argument must be all digits')
    sys.exit(1)

print(num)
while num != '1':
    if num[-1:] in '13579':
        print('Reached odd number, therefore cannot be power of two')
        sys.exit(0)
    num = half(num)
    print(num)

print('Reached 1, was therefore power of two')

Running that with various (numeric) arguments will show you the process, such as with:

pax$ python ispower2.py 65534
65534
32767
Reached odd number, therefore cannot be power of two

pax$ python ispower2.py 65536
65536
32768
16384
8192
4096
2048
1024
512
256
128
64
32
16
8
4
2
1
Reached 1, was therefore power of two

---

^(a) Take, for example, the number 34. Half of the 3 is 1.5 so the 1 can be used to affect that specific digit position but the "half" left over can simply be used by bumping up the digit on the right by five after halving it. So the 4 halves to a 2 then has five added to make 7. And half of 34 is indeed 17.

Answer 3

A bit better solution that I could code in Java, which doesn't use any fancy object like BigInteger. This approach is same as simple way of performing division. Only look out for remainder after each division. Also trim out the leading zeroes from the quotient which becomes new dividend for next iteration.

class DivisionResult{
    String quotient;
    int remainder;
    public DivisionResult(String q, int rem){
        this.quotient = q;
        this.remainder = rem;
    }
}
public int power(String A) {
    if (A.equals("0") || A.equals("1")) return 0;
    while (!A.equals("1")){
        DivisionResult dr = divideByTwo(A);
        if (dr.remainder == 1) return 0;
        A = dr.quotient;
    }
    return 1;
}
public DivisionResult divideByTwo(String num){
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    for (int i = 0;i < num.length(); i++){
        int divisibleNum = carry*10 + (num.charAt(i) - '0');
        carry = divisibleNum%2;
        sb.append(divisibleNum/2);
    }
    return new DivisionResult(sb.toString().replaceAll("^0+(?!$)", ""), carry);
}