Сдвиг вправо для выполнения деления на 2 на -1

Question

Я знаю, что могу выполнить деление на 2, используя сдвиг вправо.

Для простоты возьмем 4-битную систему счисления

-1 - 1111
-2 - 1110
-3 - 1101
-4 - 1100
-5 - 1011
-6 - 1010
-7 - 1001
-8 - 1000
7  - 0111
6  - 0110
5  - 0101
4  - 0100
3  - 0011
2  - 0010
1  - 0001
0  - 0000

Если я попытаюсь выполнить

6 / 2 = 0110 >> 1 = 0011 = 3
-6/ 2 = 1010 >> 1 = 1101 = -3

Действителен как для + ve, так и для -ve числа

Однако, когда приходят к 1

1 / 2 = 0001 >> 1 = 0000 = 0
-1/ 2 = 1111 >> 1 = 1111 = -1

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

В настоящее время мне нужно поставить специальную проверку if, поскольку я ожидаю -1 / 2 = 0.

Мне было интересно, как вы справляетесь с этим исключением в вашем коде? Парень, если поставить чек?

Answer 1

Любое отрицательное нечетное число не будет работать. Однако, чтобы ответить на ваш вопрос, если вы знаете, что у вас могут быть отрицательные числа, просто разделите на 2. Это превращается в сдвиг с исправлением в jit / compiler.

Answer 2

@ Анон технически правильный.

Тем не менее, рекомендуется использовать оператор / для деления и оставить микрооптимизацию JIT-компилятору. JIT-компилятор способен оптимизировать деление на константы как последовательности сдвига / добавления ... , когда это оптимально для платформы исполнения .

Подобные действия (вероятно) являются преждевременной оптимизацией, и это может быть антиоптимизацией, если ваш код должен работать быстро на нескольких платформах Java.

Answer 3

Мне стало скучно один день, и я делю профили против сдвигов для власти 2 вещей; думал, что я опубликую это здесь для всех, кто заинтересован.

На HotSpot VM 1.6 в Windows использование j /= 4 в диапазоне от -100000000 до 100000000 выполнялось примерно за 12 секунд, а при использовании j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1; - всего 2,5 секунды

OpenJDK VM 1.6 в Linux получил 5,5 с для делений и 1,5 с для смен.

Это предполагает, что JIT-компилятор на самом деле не делает ничего особенного для степени 2 деления.

GCC удалось оптимизировать деление так, чтобы оно было быстрее, чем сальто и смены.

~(~j+1 >> 2) + 1 использует двойное дополнение, чтобы перевернуть положительное число, сдвинуть и перевернуть его обратно.

long j = 0;
for (long i = -100000000; i < 100000000; i++) {
    j = i;
    j /= 4;
}
System.out.println(j);`

против

long j = 0;
for (long i = -100000000; i < 100000000; i++) {
    j = i;
    j = (j >= 0) ? j >> 2 : ~(~j+1 >> 2) + 1;
}
System.out.println(j);`

Answer 4

Мне неприятно это говорить, но я не обращаюсь с этим в моем коде, поскольку я не использую сдвиг битов для умножения или деления. Это пахнет для меня преждевременной оптимизации .

Почему вы думаете, что вам нужно делать деление с битовым смещением, а не более читаемым x / 2?

Answer 5

Если вы смещаете вправо, чтобы разделить на два, вы всегда заканчиваете тем, что «округлите» вниз - к нулю, если положительный, от него, если отрицательный.

Если это не то, что вы хотите, вы можете исправить это:

if (n & 1 > 0 && n < 0)
    result += 1;

Answer 6

В нечетном случае обе операции приводят к операции на полу в результате.

• 3/2 -> этаж (1,5) => 1
• -3 / 2 -> этаж (-1,5) => -2

Вы можете поставить чек, что-то вроде \

if ( isOdd(number) && isNegative(number) )
   result++;