Как побитовые операторы AND OR и XOR работают с целыми числами со знаком?

Question

Я просто решал случайные задачи на bitwise operators и пробуя различные другие комбинации для создания личных заметок. И почему-то я просто не могу найти решение.

Скажем, я хотел проверить побитовое И между двумя целыми числами или по ~ числу и -отрицательному числу (~num1 & -num2) и различным другим комбо. Тогда я вижу ответ, но я не смог установить, как это произошло?

Приставка:

console.log (25 и 3); выходы 1 (я могу решить это легко).

console.log (-25 и -3); Выходы-27.

так же

console.log(~25 и ~3); выходы -28.

console.log (25 и ~3); выходы -24.

console.log(~25 и 3); выходы -2.

console.log(~25 и -3); выходы --28.

console.log (-25 и ~3); выходы --28.

Я знаю логику "console.log (25 & -3)".

25 это 11001
-3 это 11101(3=00011 Знак минус как комплимент 2с + 1)
AND-11001 = 25.

Но я не могу заставить его работать одинаково, когда оба числа отрицательны или в других случаях, упомянутых выше. Я пробовал разные комбинации чисел, а не только эти два. Но я не могу решить проблему. Может кто-нибудь объяснить бинарную логику, используемую в задачах, которые я не могу решить.

(Я потратил около 2 часов здесь на SO, чтобы найти ответ, и еще 1 час + на Google, но я до сих пор не нашел ответа).

Спасибо и С уважением.

Answer 1

JavaScript указывает, что побитовые операции над целыми числами выполняются так, как если бы они хранились в двоичной записи. К счастью, в настоящее время большинство компьютерного оборудования использует эту нотацию изначально.

Для краткости я собираюсь показать следующие числа в виде 8-битного двоичного кода. Они на самом деле 32-битные в JavaScript, но для чисел в исходном вопросе это не меняет результат. Это, однако, позволяет нам отбросить много ведущих битов.

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

Настоящий ключ к пониманию этого заключается в том, что вы не используете битовые операции над целыми числами. Вы используете их на пакетах с битами определенного размера, и эти пакеты с битами удобно представить в виде целых чисел. Это ключ к пониманию того, что здесь происходит, потому что вы наткнулись на случай, когда разница имеет значение.

В компьютерной науке существуют особые обстоятельства, когда вы можете манипулировать пакетами с битами способами, которые по совпадению дают те же результаты, как если бы вы выполняли определенные математические операции над числами. Но это работает только в определенных обстоятельствах, и они требуют, чтобы вы предположили определенные вещи о числах, над которыми вы работаете, и если ваши числа не соответствуют этим предположениям, все рушится.

Это одна из причин, по которой Дональд Кнут сказал, что "преждевременная оптимизация - корень всего зла". Если вы хотите использовать побитовые операции вместо действительной целочисленной математики, вы должны быть абсолютно уверены, что ваши входные данные действительно будут соответствовать предположениям, необходимым для работы этого трюка. В противном случае результаты начнут выглядеть странно, когда вы начнете использовать входные данные вне этих предположений.

Answer 2

25 = 16+8+1 = 0b011001Я добавил еще одну цифру 0 в качестве знака. Практически у вас будет по крайней мере 8 двоичных цифр, но математика дополнения этих двух одинакова. Чтобы получить -25 в дополнении 6-бит два, вы должны сделать -25 = ~25 + 1=0b1001113=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 3

Двоичное строковое представление 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); })

Answer 4

-27 содержит 6 двоичных цифр, поэтому вы должны использовать числа с как минимум таким количеством цифр. С 8-битными числами имеем:

• 00011001 = 25
• 00000011 = 3
• 00011011 = 27

а также:

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

Теперь -25 & -3 = -27, потому что 11100111 & 11111101 = 11100101