检查命令行中的数字是否为 2 的幂

Question

我无法制作一个 bash 脚本来检查命令行中的输入数字是否为 2 的幂

输入

# ./pow2script.sh xyzdf 4 8 12 -2 USAD

期望的输出：期望的输出应该在单独的行上

4
8

因为只有 4 是 2^2 而 8 是 2^3

pow2script.sh 的内容

#!/bin/bash

function is_power_of_two () {
    declare -i n=$1
    (( n > 0 && (n & (n - 1)) == 0 ))
}

for number; do
    if is_power_of_two "$number"; then
        printf "%d\n" "$number"
    fi
done

Answer 1

有一个很好的快捷方式来检查一个数字是否是 2 的幂。

如果用二进制表示这样的数字，它将是单个 1 后跟一串零，例如0b100000数字 32。你有 1，例如0b011111数字 31，它是 32 - 1。如果你对这两个进行按位和运算，你会得到一个零。该属性仅对 2（和零）的幂的数字有效。

所以：

function is_power_of_two () {
    declare -i n=$1
    (( n > 0 && (n & (n - 1)) == 0 ))
}

将其用作：

for number; do
    if is_power_of_two "$number"; then
        printf "%d\n" "$number"
    fi
done

和执行输出：

$ ./power2.sh 1 2 3 4 5 7 8 9 31 32 33 -2
1
2
4
8
32

Answer 2

如果它的汉明权恰好是 1，则该数字是 2 的幂。

计算一个数的汉明权与计算其二进制表示中 1 的个数相同。

以下是执行此操作的简短bash脚本：

#!/bin/bash

# loop over all numbers on the command line
# note: we don't verify that these are in fact numbers
for number do
    w=0         # Hamming weight (count of bits that are 1)
    n=$number   # work on $n to save $number for later

    # test the last bit of the number, and right-shift once
    # repeat until number is zero
    while (( n > 0 )); do
        if (( (n & 1) == 1 )); then
            # last bit was 1, count it
            w=$(( w + 1 ))
        fi

        if (( w > 1 )); then
            # early bail-out: not a power of 2
            break
        fi

        # right-shift number
        n=$(( n >> 1 ))
    done

    if (( w == 1 )); then
        # this was a power of 2
        printf '%d\n' "$number"
    fi
done

测试：

$ bash script.sh xyzdf 4 8 12 -2 USAD
4
8

注意：有更有效的方法可以做到这一点，并且bash是一种特别糟糕的语言选择。

由于它在短时间内出现了几次（这似乎是家庭作业或其他类型的练习）：

• 1如果它出现在输入中，我不会修改此代码以跳过该数字。
• 我不会让它以任何形式输出数字的总和。
• 除了评论中已经完成的内容之外，我不会进一步描述该算法。