0

我正在尝试计算一个字节中设置的位数，但我似乎遇到了一些我找不到答案的问题。

我的代码目前看起来像

   public static int numBits(byte input){
       int count = 0;
       while (input != 0){
           if ((input & 1)==1){
               count++;
           }
           input >>= 1;
       }
       return count;
   }

在我尝试之前它似乎工作正常x = -1。

这最终创建了一个无限循环，因为正在插入值 1 位。所以我偶然发现

Java：负数右移

我的解释意味着我应该使用input >>>= 1;，但这仍然导致无限循环。

所以我试图通过尝试弄清楚发生了什么

byte x = -1;
System.out.println(x >>> 1);
System.out.println(x >> 1);

这导致

2147483647
-1

让我更加困惑。这个数字2147483647是从哪里来的，我可能在哪里犯了逻辑错误？

4

3 回答 3

4

运算符的>>>意思是向右移动，但不要符号扩展。

您的试验非常接近，但您实际上并没有修改x，所以您可以这样做：

int x = -1;
x = x >>> 1;
System.out.println(x);
x = x >> 1; // highest bit = 0 now
System.out.println(x);

哪个会产生

2147483647
1073741823

请注意，我使用的是int而不是byte这里，因为位移的结果会强制输入至少为整数大小。

有趣的是，当你运行时：

byte input = -1;
input = (byte) (input >>> 1);

结果还是 -1。这是因为上面提到的这个操作符发生了类型强制。为防止这种情况影响您，您可以屏蔽 的位input以确保您只取前 8 个：

byte input = -1;
input = (byte) ((input & 0xFF) >>> 1);

把它放在一起，如果你要运行：

byte input = -1;
input = (byte) ((input & 0xFF) >>> 1);
System.out.println(input);
input = (byte) ((input & 0xFF) >> 1);
System.out.println(input);

你会得到预期的结果：

127
63
于 2013-09-13T03:12:04.423 回答
3

这都是由有符号整数存储为二进制值的方式引起的。数字的最高位确定符号的方式（有点——零使事情变得奇怪），并且符号通过算术移位保留。您的打印语句给出了奇怪的结果，因为结果被提升为int值而不是字节。

如果您想要一个非常简单的解决方法，您可以使用 anint来存储您的值，但请确保屏蔽除最低字节之外的所有内容：

public static int numBits(byte inByte){
   int count = 0;
   int input = inByte & 0xFF;
   while (input != 0){
       if ((input & 1)==1){
           count++;
       }
       input >>= 1;
   }
   return count;
}

就像我在上面的评论中所说的那样，您应该真正阅读二进制中带符号数字的二进制补码表示。如果您了解负数的表示方式以及算术/逻辑移位之间的区别，那么所有这些都将非常有意义。

于 2013-09-13T03:23:38.053 回答
1

您可能会发现 JVM 的实际工作方式很有趣。注意：只有 8 位，所以你真的不需要循环。

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

注意：在 x86/x64 上，JVM 将其替换为内部函数。即它使用单个机器代码指令。如果您复制此方法并比较它将调用原始方法，则速度会慢 3 倍，因为 JVM 仅替换硬编码的方法列表，因此它将替换 Integer.bitCOunt，而不是副本。

简而言之，使用内置方法而不是重新发明它。

于 2013-09-13T07:32:31.340 回答