Правый сдвиг для выполнения деления на 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 числа

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

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

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

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

мне было интересно, как же парень обработать это исключение в коде? Вы, парень, поставили чек?

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

@Anon технически корректен.

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

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

Answer 6

Мне было скучно в один прекрасный день, и профилированные деления против смены на мощность 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.5s для делений и 1.5s для смены.

Это предполагает, что компилятор 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);`