найти следующую мощность 2 для отрицательного числа

Question

Эй, ребята я делал исследование по расчету следующей степени двойки и наткнулся на код, который выглядит следующим образом:

int x;//assume that x is already initialized with a value 
--x; 
x |= x >> 1; 
x |= x >> 2; 
x |= x >> 4; 
x |= x >> 8; 
x |= x >> 16; 
return x+1; 

Он отлично работает, когда я бегу с положительные числа, но это не работает с отрицательными числами, которые я не понимаю, потому что я думаю, что не имеет значения, положительно или отрицательно ли это число в плане нахождения для него следующей силы. Если у нас есть число 5, и мы хотим найти следующую мощность 2. Если мы будем интуитивно думать об этом, мы знаем, что его 8, потому что 8 больше 5 и 8, совпадает с 2^3. Если я попытаюсь использовать отрицательное число, я всегда буду получать 0, который я не понимаю, потому что 0 не является степенью двух

Answer 1

Короткий ответ заключается в том, что в стандарте C++ указано, что значение, полученное от оператора >>, при отрицательных значениях реализуется, тогда как на положительных значениях это результат деления на мощность 2.

Термин «реализация, определенная», упрощенно, означает, что стандарт разрешает результат варьироваться между реализациями, т.е. между компиляторами. Между прочим, это означает отсутствие гарантии того, что он будет вести себя так же, как и для положительных значений (для которых поведение однозначно указано).

Причина в том, что представление объекта signed int также определено в реализации. Это позволяет, например, использовать представление двойного дополнения, которое (хотя иногда используются другие представления) довольно часто используется на практике.

Математически, сдвиг вправо в двойном дополнении эквивалентен делению на две силы с округлением вниз до бесконечности, а не к нулю. Для положительного значения округление к нулю и к -infinity имеют одинаковый эффект (как нуль, так и -инфекция меньше любого положительного целочисленного значения). Для отрицательного значения они не (округление от нуля, а не к нулю).

Answer 2

Питер дал вам толкование кода, основанного на том, что вы стоите вокруг. Вот еще один, более побитовый, один:

Последовательные сдвиги в этом коде «заполняются» с 1-м позицией всех бит ниже самой высокой, установленной в начале. Давайте посмотрим на это более подробно:

Пусть x=0b0001 ???? ???? ???? бинарное представление 16 битного числа, где ? может быть 0 или 1.

x |= x >> 1; // x = 0b0001 ???? ???? ???? | 0b0000 1??? ???? ???? = 0b0001 1??? ???? ???? 
x |= x >> 2; // x = 0b0001 1??? ???? ???? | 0b0000 011? ???? ???? = 0b0001 111? ???? ???? 
x |= x >> 4; // x = 0b0001 111? ???? ???? | 0b0000 0001 111? ???? = 0b0001 1111 111? ???? 
x |= x >> 8; // x = 0b0001 1111 111? ???? | 0b0000 0000 0001 1111 = 0b0001 1111 1111 1111 

Следовательно, сдвиги дают вам номер из форма 0b00...011...1, то есть только 0 с, то только 1 с, что означает номер формы 2^n-1. Вот почему вы добавляете 1 в конце, чтобы получить мощность 2. Чтобы получить правильный результат, вам также необходимо удалить 1 с самого начала, чтобы компенсировать тот, который вы добавите в конце.

Теперь для отрицательных чисел стандарт C++ не определяет, какие наиболее значимые биты должны быть при правом смещении. Но являются ли они 1 или 0 не имеет значения в данном конкретном случае, до тех пор, как ваше представление отрицательных чисел используется в его наиболее значимых битовых позициях в 1, то есть почти все из них. *

потому что вы всегда or х с сам, все эти самые левые биты (где сдвиги отличаются) будут or ed с 1 s.В конце алгоритма вы вернетесь 0b11111...1 + 1, который в вашем случае означает 0 (потому что вы используете дополнение 2s, результатом будет 1 в дополнении 1s и -2 ^{количество бит - 1} + 1 в знаке-величине).

_{* Это справедливо для представлений основных отрицательных чисел, от большинства до наименее популярных: то есть дополнения 2s, знака-величины и дополнения 1s. Примером, где это не так, является избыточное представление K, которое используется для индексов с плавающей запятой IEEE.}