Определение количества битов, необходимых для представления дополнения 2 с использованием только побитовых функций - PullRequest
Новая
       44

Определение количества битов, необходимых для представления дополнения 2 с использованием только побитовых функций

0 голосов
/ 03 февраля 2012

Мы можем предположить, что int равен 32 битам в комплименте 2 Единственные операторы Legal:!~ & ^ |+ << >>

На данный момент я использую грубую силу 

int a=0x01;
x=(x+1)>>1; //(have tried with just x instead of x+1 as well)
a = a+(!(!x));

... с последними 2 заявлениями, повторенными 32 раза.Это добавляет 1 к каждому разу, когда x смещается на одно место и! = 0 для всех 32 битов

Используя тестовый компилятор, он говорит, что мой метод завершается ошибкой в ​​тестовом примере 0x7FFFFFFF (0 сопровождается 31 1) и говорит это числотребуется 32 бита для представления.Я не понимаю, почему это не 31 (который вычисляет мой метод) Кто-нибудь может объяснить, почему?И что мне нужно изменить, чтобы учесть это?

Ответы [ 2 ]

2 голосов
/ 19 апреля 2013

Попробуйте этот код, чтобы проверить, можно ли вписать целое число со знаком x в n бит. Функция возвращает 1, когда это происходит, и 0 в противном случае. 

// http://www.cs.northwestern.edu/~wms128/bits.c
int check_bits_fit_in_2s_complement(signed int x, unsigned int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask))>> (n + ~0));
}
2 голосов
/ 03 февраля 2012

0x7FFFFFFF требует 32 бита.Это может быть выражено как целое число без знака всего в 31 бите: 

111 1111 1111 1111 1111 1111 1111 1111

, но если мы интерпретируем это как целое число со знаком, используя дополнение к двум, то ведущий 1 будет указывать, чтоэто отрицательно.Таким образом, мы должны добавить начальный 0: 

0 111 1111 1111 1111 1111 1111 1111 1111

, который затем делает его 32-битным.

Что касается того, что вам нужно изменить - ваша текущая программа на самом деле имеет неопределенное поведение.Если 0x7FFFFFFF (2 31 -1) является максимально допустимым целочисленным значением, тогда 0x7FFFFFFF + 1 не может быть вычислено.Это может привести к -2 32 , но нет абсолютно никакой гарантии: стандарт позволяет компиляторам делать абсолютно все в этом случае, а реальные компиляторы действительно выполняют оптимизацию, которая может привести к шокирующим последствиям.результаты, когда вы нарушаете это требование.Точно так же нет конкретной гарантии того, что будет означать ... >> 1, если ... отрицательно, хотя в этом случае компиляторы обязаны, по крайней мере, выбрать конкретное поведение и задокументировать его.(Большинство компиляторов предпочитают создавать другое отрицательное число, копируя самый левый бит 1, но это не гарантируется.)

Так что действительно единственное надежное исправление:

  • переписать ваш код в целом, используя алгоритм, который не имеет этих проблем;или
  • , чтобы специально проверить случай, когда x равен 0x7FFFFFFF (возвращает жестко закодированный 32), и случай, когда x отрицателен (заменив его на ~x, то есть -(x+1)и продолжаем как обычно).
...