按位 AND OR 和 XOR 如何处理 -negative 有符号整数？

Question

我只是在 bitwise operators 上解决随机问题并尝试各种其他组合来做个人笔记。不知何故，我就是想不出解决办法。

假设我想检查两个整数之间的按位与或 ~number 和 -negative number(~num1 & -num2) 以及各种其他组合。然后我可以看到答案，但我无法确定这是怎么发生的？

控制台：

console.log(25 & 3); outputs 1 (I can solve this easily).

console.log(-25 & -3); outputs-27.

同理

console.log(~25 & ~3); outputs -28.

console.log(25 & ~3); outputs -24.

console.log(~25 & 3); outputs -2.

console.log(~25 & -3); outputs --28.

console.log(-25 & ~3); outputs --28.

我知道 "console.log(25 & -3)".

背后的逻辑

25 is 11001
-3 is 11101(3=00011 The minus sign is like 2s compliment+1)
AND-11001 = 25.

但是当两个数字都是负数或上面提到的其他情况时，我不能让它以同样的方式工作。我也尝试过各种数字组合，而不仅仅是这两个。但我无法解决问题。谁能解释一下我无法解决的问题中使用的二进制逻辑。

（我在 SO 上花了大约 2 小时找到答案，在 google 上又花了 1 小时以上，但我仍然没有找到答案）。

感谢和问候。

Answer 1

-27 中有 6 个二进制数字，因此您应该使用至少有那么多数字的数字。对于 8 位数字，我们有：

00011001 = 25
00000011 = 3
00011011 = 27

和：

11100111 = -25
11111101 = -3
11100101 = -27

现在 -25 & -3 = -27 因为 11100111 & 11111101 = 11100101

Answer 2

JavaScript 指定对整数执行按位运算，就像它们存储在补码符号中一样。幸运的是，现在大多数计算机硬件本身都使用这种表示法。

为了简洁起见，我将以下数字显示为 8 位二进制。它们在 JavaScript 中实际上是 32 位的，但对于原始问题中的数字，这不会改变结果。但是，它确实让我们放弃了很多前导位。

console.log(-25 & -3); //outputs -27. How?

如果我们将整数写成二进制，我们将分别得到 (11100111 & 11111101)。将它们加在一起得到 11100101，即 -27。

在您后面的示例中，您似乎交替使用了 NOT 运算符 (~) 和否定 (-)。你不能用二进制补码来做到这一点：~ 和 - 不是一回事。 ~25 是 11100110，也就是 -26，不是 -25。同样，~3是11111100，也就是-4，不是-3。

但是当我们把这些放在一起时，我们可以计算出你给出的例子。

console.log(~25 & ~3); //outputs-28. How?

11100110 & 11111100 = 11100100，即 -28（不是你写的 28）

console.log(25 & ~3);//outputs-24. How?

00011001 & 11111100 = 00011000, 即 24

console.log(~25 & 3);//outputs-2. How?

11100110 & 00000011 = 00000001，即 2

console.log(~25 & -3);//outputs--28. How?

11100110 & 11111101 = 11100100, 即-28

console.log(-25 & ~3);//outputs--28. How?

11100111 & 11111100 = 11100100, 即-28

理解这一点的真正关键是 您实际上并没有对整数使用按位运算。您将它们用于特定大小的比特袋，而这些比特袋恰好可以方便地表示为整数。这是了解此处发生的事情的关键，因为您偶然发现了差异很重要的情况。

在计算机科学中存在特定情况，您可以通过巧合的方式来处理比特包，得到与您对计算机进行特定数学运算相同的结果数字。但这仅适用于特定情况，并且它们要求您对正在处理的数字做出某些假设，如果您的数字不符合这些假设，事情就会崩溃。

这是 Donald Knuth 说 "premature optimization is the root of all evil" 的原因之一。如果您想使用按位运算代替实际的整数数学运算，您必须绝对确定您的输入实际上会遵循该技巧起作用所需的假设。否则，当您开始使用这些假设之外的输入时，结果会开始看起来很奇怪。

Answer 3

25 = 16+8+1 = 0b011001，我又加了0位作为符号位。实际上你至少有 8 个二进制数字但两者的补码数学是一样的。要在 6 位二进制补码中获得 -25，您需要 -25 = ~25 + 1=0b100111 3=2+1=0b000011; -3 = ~3+1 = 0b111101

当你 & 这两个时，你会得到：

-25 = ~25 + 1=0b100111
&
-3 = ~3 + 1 = 0b111101
              0b100101

最左边的位（符号位）已设置为负数。要找到它的负数，您可以反转过程并首先减去 1，然后执行 ~.

~(0b100101-1) = 0b011011

那就是 1+2+0*4+8+16 = 27 所以 -25&-3=-27。

对于 25 & ~3，是：

25 = 16+8+1 = 0b011001
&        ~3 = 0b111100
______________________
              0b011000 = 24

对于 ~25 和 3，它是：

~25 =         0b100110
&        ~3 = 0b000011
______________________
              0b000010 = 2

对于 ~25 和 -3，它是：

~25 =         0b100110
&      ~3+1 = 0b111101
______________________
               0b100100 #negative

#find what it's a negative of:
~(0b100100-1) =~0b100011 = 0b011100 = 4+8+16 = 28
               0b100100 = -28

Answer 4

32 位整数的二进制字符串表示可以通过以下方式找到：

(i >>> 0).toString(2).padStart(32, '0')

两个二进制字符串的按位与运算很简单

带符号的 32 位二进制字符串的整数值是

parseInt(bitwiseAndString, 2)

如果字符串以“0”开头，或者

-~parseInt(bitwiseAndString, 2) - 1

如果以“1”开头

将所有这些放在一起：

const tests = [
  ['-25', '-3'],
  ['~25', '-3'],
  ['25', '~3'],
  ['~25', '3'],
  ['~25', '~3'],
  ['-25', '~3']
]

const output = (s,t) => { console.log(`${`${s}:`.padEnd(20, ' ')}${t}`); }

const bitwiseAnd = (i, j) => {
  console.log(`Calculating ${i} & ${j}`);
  const bitStringI = (eval(i) >>> 0).toString(2).padStart(32, '0');
  const bitStringJ = (eval(j) >>> 0).toString(2).padStart(32, '0');
  output(`bit string for ${i}`, bitStringI);
  output(`bit string for ${j}`, bitStringJ);
  const bitArrayI = bitStringI.split('');
  const bitArrayJ = bitStringJ.split('');
  const bitwiseAndString = bitArrayI.map((s, idx) => s === '1' && bitArrayJ[idx] === '1' ? '1' : '0').join('');
  output('bitwise and string', bitwiseAndString);
  const intValue = bitwiseAndString[0] === '1' ? -~parseInt(bitwiseAndString, 2) - 1 : parseInt(bitwiseAndString, 2);
  if (intValue === (eval(i) & eval(j))) {
    console.log(`integer value: ${intValue} ✓`);
  } else {
    console.error(`calculation failed: ${intValue} !== ${i & j}`);
  }
}

tests.forEach(([i, j]) => { bitwiseAnd(i, j); })

按位 AND OR 和 XOR 如何处理 -negative 有符号整数？

How does bitwise AND OR and XOR works on -negative signed integers?

javascript

bit-manipulation

bitwise-operators

bitwise-and