检查整数是否为2的幂次方并返回它。

huangapple go评论72阅读模式
英文:

Check if int is a power of 2 and return it

问题

以下是翻译好的部分:

我有一个《尼姆游戏》的程序,在这个游戏中,两名玩家轮流从一堆小球中取走小球。每位玩家必须取走 1 个小球,但不能超过剩余小球数量的一半。

有三种类型的玩家:人类玩家、愚蠢的计算机玩家和智能计算机玩家。

我在智能计算机类的部分遇到了问题。智能计算机应该取走恰好足够的小球,使剩余堆大小成为 2 的幂减一。(1、3、7、15)。

我需要帮助判断智能计算机希望移除的整数是否是 2 的幂次。

这是我实现了 Player 接口的 SmartComputer 类。

/**
 * 实现了接口 player,返回从堆中取走的小球数量和玩家姓名
 */
class SmartComputer implements Player {

    /**
     * @param marbles 接收堆中小球的数量
     * @return 从堆中取走的小球数量
     */
    public int move(int marbles) {
        int remove;
        int power = 2;

        // 如果小球数量大于 3,那么执行以下操作
        if (marbles > 3) {

            while (power < marbles) {
                power = power * 2;
            }

            power /= 2;

            remove = power - 1;

            return remove;
        }
        return 1; // 暂时的返回值
    }

    public String playerName(String name) {
         return "智能计算机"; // 暂时的返回值
    }
}

注意:上面的翻译中,代码部分并未进行翻译。

英文:

I have this program of Game of Nim where 2 players take turns removing marbles from a pile. Each player must remove 1 but no more than half of remaining marbles in the pile.

There are 3 type of players: Human, Dumb Computer, and Smart Computer.

I'm having trouble with the smart computer class. The smart computer is supposed to remove exactly enough marbles to make the remaining pile size a power of two minus one. (1, 3, 7, 15).

I need help on how to check if int that smart computer wants to remove is a power of 2.

Here is my SmartComputer class that implements Player interface

/**
 * Implements interface player Returns amount of marbles taken from pile and
 * players name
 */
class SmartComputer implements Player {

    /**
     * @param marbles receives amount of marbles in pile
     * @return number of marbles to remove from pile
     */
    public int move(int marbles) {
        int remove;
        int power = 2;
        //int div;
        //boolean check;

        //if marbles is less than 3 then just return 1
        if (marbles &gt; 3) {

            while (power &lt; marbles) {
                 power = power * 2;
            }

            power /= 2;

            remove = power - 1;

            return remove;
        }
        return 1; // temporary
    }

    public String playerName(String name) {
         return &quot;Smart Computer&quot;; //temporary
    }
}

答案1

得分: 1

要找出需要减去多少个弹珠,我们需要找到最大的(2^n-1),其值小于弹珠的数量。注意,2的幂次减1的结果在二进制表示中所有位都是"1",而2的幂次在二进制表示中只有一位是"1"。

  • 1的二进制表示是1,2的二进制表示是10
  • 3的二进制表示是11,4的二进制表示是100
  • 7的二进制表示是111,8的二进制表示是1000
  • 15的二进制表示是1111,16的二进制表示是10000
  • 31的二进制表示是11111,32的二进制表示是100000

因此,为了实现这一点,我们首先找到最高位的"1"位的位置,然后使用位移运算计算2的该位置次幂。这会给出最大的2的幂,其值小于或等于marble

int positionOfHighestOne = Integer.highestOneBit(marbles) - 1;
int nearestPowerOf2 = 1 << positionOfHighestOne;

现在我们可以通过减去来轻松获得比该值小1的值:

int nearestOneLessThanPowerOf2 = nearestPowerOf2 - 1;
int marblesToSubtract = marbles - nearestOneLessThanPowerOf2;
return marblesToSubtract;
英文:

To find how many marbles we need to subtract, we need to find the largest (2^n-1) that is less than the number of marbles. Observe that one less than a power of 2 has all "1"s as the binary presentation, and powers of 2 have a single "1" in their binary representations.

  • 1 is 1 in binary, 2 is 10 in binary
  • 3 is 11 in binary, 4 is 100 in binary
  • 7 is 111 in binary, 8 is 1000 in binary
  • 15 is 1111 in binary, 16 is 10000 in binary
  • 31 is 11111 in binary, 32 is 100000 in binary

So to do this, we first find the position of the most significant "1" bit, and calculate 2 to the power of that position using a bit shift. This gives the largest power of 2 that is less than or equal to marble.

int positionOfHighestOne = Integer.highestOneBit(marbles) - 1;
int nearestPowerOf2 = 1 &lt;&lt; positionOfHighestOne;

Now we can easily get one less than that by subtracting:

int nearestOneLessThanPowerOf2 = nearestPowerOf2 - 1;
int marblesToSubtract = marbles - nearestOneLessThanPowerOf2;
return marblesToSubtract;

huangapple
  • 本文由 发表于 2020年10月26日 10:00:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/64530616.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定