英文:
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 > 3) {
while (power < marbles) {
power = power * 2;
}
power /= 2;
remove = power - 1;
return remove;
}
return 1; // temporary
}
public String playerName(String name) {
return "Smart Computer"; //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 << positionOfHighestOne;
Now we can easily get one less than that by subtracting:
int nearestOneLessThanPowerOf2 = nearestPowerOf2 - 1;
int marblesToSubtract = marbles - nearestOneLessThanPowerOf2;
return marblesToSubtract;
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论