Разделите целое число со знаком на 2

Question

Я работаю над тем, как разделить знаковое целое на 2, используя только двоичные операторы (< < >> +^~ & |!), И результат чтобы округлить до нуля. Я столкнулся с this question также от Stackoverflow по проблеме, однако я не могу понять, почему это работает. Вот решение:

int divideByPowerOf2(int x, int n) 
{ 
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n; 
} 

Я понимаю x >> 31 части (только добавить следующую часть, если x отрицательные, потому что если он положительный x будет автоматически круглым в направлении 0). Но меня беспокоит часть (1 << n) + ~0. Как это работает?

Answer 1

Предполагая 2-дополнение, только бит сдвига дивиденд эквивалентно определенного рода деление: не условное деление, где мы обогнуть дивиденд следующего кратного делителя к нулю. Но другой вид, где мы крутим дивиденд к отрицательной бесконечности. Я заново открыл это в Smalltalk, см. http://smallissimo.blogspot.fr/2015/03/is-bitshift-equivalent-to-division-in.html.

Например, давайте разделим -126 на 8. Традиционно, мы должны написать

-126 = -15 * 8 - 6 

Но если мы округляем к бесконечности, мы получим положительный остаток и записать его:

-126 = -16 * 8 + 2 

бит-сдвиг выполняет вторую операцию в отношении битовых шаблонов (предположительно 8 бит длиной int для краткости):

1000|0010 >> 3 = 1111|0000 
1000|0010  = 1111|0000 * 0000|1000 + 0000|0010 

Итак, что, если мы хотим традиционное деление с округлением до нуля и остатком того же знака, что и дивиденд? Простой, нам просто нужно добавить 1 к частному - тогда и только тогда, когда дивиденд отрицательный, а деление неточно.

Вы видели, что x>>31 соответствует первому условию, дивиденд отрицательный, если int имеет 32 бита.

Второй термин соответствует второму условию, если деление неточно.

Посмотрите, как закодированы -1, -2, -4, ... в двух частях: 1111 | 1111, 1111 | 1110, 1111 | 1100. Таким образом, отрицание n-й степени двух имеет n конечных нулей.

Когда дивиденд имеет n конечных нулей, и мы делим на 2^n, то не нужно добавлять 1 к конечному частному. В любом другом случае нам нужно добавить 1.

Что ((1 < < n) + ~ 0) делает создание маски с n конечными.

n последних бит не имеет значения, потому что мы собираемся сдвинуться вправо и просто выбросить их. Итак, если деление является точным, n конечных бит дивидендов равны нулю, и мы просто добавляем n 1s, которые будут пропущены. Напротив, если деление неточно, то один или несколько из n конечных бит дивиденда равны 1, и мы обязательно вызываем перенос в позицию n + 1 бит: так мы добавляем 1 к частному (мы добавляем 2^п к дивиденду). Объясняет ли это это немного больше?

Answer 2

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

Например, разделим число на 8 (сдвиг вправо на 3). Если число отрицательное, нормальные правые смены в неправильном направлении. Давайте «исправить», добавив ряд:

int divideBy8(int x) 
{ 
    if (x >= 0) 
     return x >> 3; 
    else 
     return (x + whatever) >> 3; 
} 

Здесь вы можете придумать математическую формулу для whatever, или же проб и ошибок. Во всяком случае, здесь whatever = 7:

int divideBy8(int x) 
{ 
    if (x >= 0) 
     return x >> 3; 
    else 
     return (x + 7) >> 3; 
} 

Как объединить эти два случая? Вам нужно сделать выражение, которое выглядит следующим образом:

(x + stuff) >> 3 

где stuff составляет 7 для отрицательного x, и 0 для положительных x. Хитрость здесь используется x >> 31, который представляет собой 32-разрядное число, чьи биты равны знаковому-бит x: все 0 или все 1. Так stuff является

(x >> 31) & 7 

Объединяя все эти, и заменяя 8 и 7 по более общей мощности 2, вы получаете код, о котором вы просили.

---

Примечания: в приведенном выше описании, я полагаю, что int представляет собой 32-битный аппаратный регистр, и аппаратное обеспечение использует комплемент представление двоек сделать сдвиг вправо.

Answer 3

Ссылка OP содержит код C# и так много тонких различий, которые вызывают его код с C, поскольку это сообщение отмечено.

int не обязательно 32 бит, поэтому использование магического числа 32 не обеспечивает надежного решения.

В частности, (1 << n) + ~0 приводит к выполнению определенного поведения, когда n вызывает смещение бит в место знака. Неплохое кодирование.

Ограничение кода только с помощью «бинарные» операторы << >> +^~ & | ! поощряет кодировщик к предположить вещи о int, который не является портативным и не совместим с C спецификации. Таким образом, опубликованный код OP не «работает» вообще, хотя может работать во многих общих реализациях.

Код OP не работает, когда int не является дополнением 2, не использует диапазон [-2147483648 .. 2147483647] или когда 1 << n использует поведение реализации, которое не так ожидалось.

// weak code 
int divideByPowerOf2(int x, int n) { 
    return (x + ((x >> 31) & ((1 << n) + ~0))) >> n; 
} 

Простая альтернатива, предполагая, что long long превышает диапазон int следующим образом. Я сомневаюсь, что это встречает некоторая угол цели OP, но цели данного OP поощряют ненадежную кодировку.

int divideByPowerOf2(int x, int n) { 
    long long ill = x; 
    if (x < 0) ill = -ill; 
    while (n--) ill >>= 1; 
    if (x < 0) ill = -ill; 
    return (int) ill; 
}