c++ - 给定一个巨大的整数字符串，检查它是否是 2 的幂

Question

这个数字很大(无法容纳在 C++ 中的 unsigned long long int 的范围内)。我们如何检查？

给出了一个解决方案here但这没有多大意义。 这里的解决方案尝试将大数(表示为字符串)重复除以 2，但我不确定我是否理解结果是如何一步步达到的。 有人可以解释一下或提出更好的解决方案吗？ 我们不能使用任何外部库。

这是示例代码:

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; 
} 

我试图理解 while 循环中的过程。我知道有评论，但它们并没有真正帮助我理清逻辑。

Answer 1

让我们从弄清楚如何减半“字符串数字”开始。我们将从 128 开始作为示例。您可以依次将每个数字减半(从左边开始)，请记住奇数会影响右边的数字^(a)。因此，对于 128 中的 1，将其减半得到零，但由于它是奇数，因此应将 5 保留在存储中以添加到其右侧的数字(一旦减半):

128
 v
028

然后按如下方式将 2 减半(加回已存储的 5):

028
 v
018
 v
068

因为这并不奇怪，所以我们不为下一位存储 5，所以我们将 8 减半，如下所示:

068
 v
064

您还可以通过去掉任何前导零来简化操作。从中，您可以看到它正确地将 128 减半得到 64。

要查看一个数是否是 2 的幂，您只需保持将它减半，直到恰好达到 1。但是，如果在任何时候你得到一个奇数(以 {1, 3, 5, 7, 9} 中的数字结尾的东西)，前提是它不是个位数 1 )，它不是二的幂。

例如，以下 Python 3 代码说明了这个概念:

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')

使用各种(数字)参数运行它会向您展示该过程，例如:

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) 以数字 34 为例。 3 的一半是 1.5，因此 1 可用于影响特定数字位置，但“一半"剩下的可以简单地通过将右边的数字减半后增加五来使用。因此，4 减半为 2，然后加上 5 得到 7。 34 的一半是 确实 17。