Как представить отрицание с помощью побитовых операторов, C

Question

Предположим, у вас есть 2 числа:

int x = 1;
int y = 2;

Используя побитовые операторы, как я могу представить x-y?

Answer 1

При сравнении битов двух чисел A и B возможны три варианта.Следующее предполагает использование чисел без знака.

1. A == B: все биты одинаковы
2. A > B: старший значащий бит, который отличается между двумя числами, устанавливается в A и не в B
3. A < B: старший значащий бит, который отличается между двумя числами, устанавливается в B, а не в A

Кодможет выглядеть следующим образом

int getDifType(uint32_t A, uint32_t B)
{
  uint32_t bitMask = 0x8000000;
  // From MSB to LSB
  for (bitMask = 0x80000000; 0 != bitMask; bitMask >>= 1)
  {
    if (A & bitMask != B & bitMask)
      return (A & bitMask) - (B & bitMask);
  }
  // No difference found
  return 0;
}

Answer 2

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

Answer 3

Сравните биты слева направо, ища самые левые биты, которые отличаются.Предполагая, что машина является дополнением до двух, самый верхний бит определяет знак и будет иметь перевернутый смысл сравнения с другими битами.Это должно работать на любых двух дополнительных компьютерах:

int compare(int x, int y) {
  unsigned int mask = ~0U - (~0U >> 1); // select left-most bit
  if (x & mask && ~y & mask)
    return -1; // x < 0 and y >= 0, therefore y > x
  else if (~x & mask && y & mask)
    return 1; // x >= 0 and y < 0, therefore x > y
  for (; mask; mask >>= 1) {
    if (x & mask && ~y & mask)
      return 1;
    else if (~x & mask && y & mask)
      return -1;
  }
  return 0;
}

[Обратите внимание, что это технически не переносимо.Си не дает никаких гарантий, что подписанная арифметика будет дополнением к двум.Но вам будет сложно найти реализацию C на современном компьютере, который ведет себя по-разному.]

Чтобы понять, почему это работает, сначала сравните два числа без знака: 13d = 1101b и 11d = 1011b.(Для краткости я предполагаю 4-битный размер слова.) Самый левый отличающийся бит - это второй слева, который первый установил, а другой - нет.Поэтому первое число тем больше.Должно быть достаточно ясно, что этот принцип выполняется для всех чисел без знака.

Теперь рассмотрим два числа дополнения.Вы отрицаете число, добавляя биты и добавляя один.Таким образом, -1d = 1111b, -2d = 1110b, -3d = 1101b, -4d = 1100b и т. Д. Вы можете видеть, что два отрицательных числа можно сравнить, как если бы они были без знака.Аналогично, два неотрицательных числа также можно сравнить, как если бы они были без знака.Только когда знаки различаются, мы должны их учитывать - но если они различаются, сравнение тривиально!

Answer 4

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

int x,y;
//get x & y
unsigned int mask=1;           // make the mask 000..0001
mask=mask<<(8*sizeoF(int)-1);    // make the mask 1000..000

while(mask!=0)             
{
if(x & mask > y & mask)        
{printf("x greater");break;}
else if(y & mask > x & mask)
{printf("y greater");break;}
mask=mask>>1;                  // shift 1 in mask to the right
}

Answer 5

Первым шагом будет реализация сложения с использованием только побитовых операторов. После этого все должно быть легко. Начните с малого - что вам нужно сделать, чтобы реализовать 00 + 00, 01 + 01 и т. Д.? Иди оттуда.