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

Question

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

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

Консоль:

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

console.log (-25 & -3);output-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

Бинарное строковое представление 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 2

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 3

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

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

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

и:

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

Сейчас -25 & -3 = -27 потому что 11100111 и 11111101 = 11100101