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

Question

Мы можем предположить, что 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 (который вычисляет мой метод) Кто-нибудь может объяснить, почему? И что мне нужно изменить, чтобы учесть это?

Answer 1

Пожалуйста, попробуйте этот код, чтобы проверить, можно ли вписать целое число со знаком 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));
}

Answer 2

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³¹-1) - максимально допустимое целочисленное значение, тогда 0x7FFFFFFF + 1 не может быть вычислено. Это может привести к -2³², но нет абсолютно никакой гарантии: стандарт позволяет компиляторам делать абсолютно все в этом случае, а реальные компиляторы действительно выполняют оптимизацию, которая может привести к шокирующим результатам, когда вы нарушаете это требование, Точно так же нет конкретной гарантии, что ... >> 1 будет означать, если ... отрицательно, хотя в этом случае компиляторы обязаны, по крайней мере, выбрать конкретное поведение и задокументировать его. (Большинство компиляторов выбирают другое отрицательное число, копируя крайний левый 1 немного, но нет никаких гарантий этого.)

Так что единственное верное исправление - это либо:

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