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

Question

Я написал следующую функцию:

int divideBy2Power(int x, int y) { return (x >> y) + (x < 0 && x << (32 - y)); }

, которая должна вычислять {x / (2 ^ y)} (округление до нуля) чрезвычайно эффективным способом (т.е. без ветвления!)

В тестировании это работает для большинства входных данных, но для divideBy2Power(-2, 0) оно выдает -1.Аналогично, x=-1, y=0 производит 0 (не -1).Это работает для групп других отрицательных чисел.

Я на 32-битной машине и проверил, что x << 32 выдает ноль.

Есть идеи?

Answer 1

У вас есть два источника неопределенного поведения (UB) и один из поведения, определенного реализацией (IDB):

• x << 32 - это UB для всех x (при условии, что на вашей платформе 32-битный int).
• -2 << y - это UB для всех y.
• -2 >> y является IDB для всех y.

Таким образом, любое поведение, которое вы наблюдаете за divideBy2Power(-2, 0), полностью сводится к "случайности" (из-за отсутствия лучшего термина).

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

Answer 2

Ах, ответ очевиден, если разбить выражение:

Новый код:

#include <stdio.h>

int divideBy2Power(int x, int y)
{
    int a = x >> y;
    int b = x < 0;
    int c = x << (32-y);
    printf("a=%d\n", a); 
    printf("b=%d\n", b); 
    printf("c=%d\n", c); 
    printf("b&&c=%d\n", (b&&c));
    return a + (b && c); 
}

int main()
{
    printf("%d\n", divideBy2Power(-2, 0));
    return 0;
}

Тогда вы ясно видите, что b = 1, c = -2, поэтому b && c = 1.

Answer 3

Ваша первая проблема заключается в том, что вы добавляете результат двоичного сравнения И & & (не поразрядно);который будет либо 0, либо 1. Это бессмысленно, он использует ветвь и имеет другую сомнительную логику.

Во-вторых, см. https://stackoverflow.com/a/9874464/1110687 для объяснения того, почему это не так со знаковыми числами и чтоточно не определено поведение в этом случае.Речь идет о смещении влево, но также и о смещении вправо.

Answer 4

Возможно, вы имели в виду

int divideBy2Power(int x, int y) { return (x >> y) + ( (x < 0)& (x << (32 - y))); }

Обратите внимание на дополнительные скобки.Порядок приоритета << и >> часто не соответствует ожидаемому.