[Из песочницы] Побитовая арифметика в Java
Приветствую, дорогой читатель.
Редко, но все же задачки из собеседований и обучалок имеют практическую ценность. Так, мне понадобилось реализовать на Java альтернативу арифметическим операциям над целочисленными значениями. Благо, первые страницы поисковиков пестрят готовыми решениями побитовых аналогов, и над большинством из них голову ломать не пришлось.
Признаться, я был несколько удивлен отсутствию такого материала на Хабре (плохо искал?), потому и решил восполнить этот недостаток, со своими комментариями и дополнениями.
Прошу учесть, что в примерах с побитовыми операциями значения урезаны до полубайта: фундаментальной разницы не будет, а воспринимается легче.
Сложение
Алгоритм:
private int add(int summand, int addend)
{
/*Перенос.*/
int carry = 0x00;
/*Итерировать до тех пор, пока не закончится перенос на старший разряд.*/
while(addend != 0x00)
{
/*Выставить флаг под разрядами с установленными битами.*/
carry = (summand & addend);
/*Снять с первого слагаемого биты, разряд по которым уже учтен.*/
summand = summand ^ addend;
/*Перенос переводится в старший разряд.*/
addend = (carry << 1);
}
return summand;
}
Для начала надо вспомнить о переносе в старший разряд. В десятичной системе под его определение (для текущего разряда) подпадают значения в диапазоне от 10 до 18:
109 +
019 =
128
В двоичной же системе переносится все, что больше единицы:
0001 +
0001 =
----
0010
или так:
0011 +
0011 =
----
0110
В последнем примере первыми складываются самые младшие биты:
1 + 1 = 10(два)
Ноль остается в текущем разряде, а единица переходит в старший, где участвует в сложении:
1 + 1 + 1 = 11 (три)
младшая единица остается в текущем, старшая сдвигается дальше. Отсюда же можно вывести правило, что в двоичной системе для одного текущего разряда под перенос подпадают значения от двух до трех включительно.
В части, касающейся алгоритма, стоит обратить внимание на инструкцию определения наличия/отсутствия переноса на примере предыдущих значений:
carry = (summand & addend);
0011 = 0011 & 0011
Это еще не перенос, но выставление «флагов» над разрядами, сложение которых оставляет перенос.
Коль скоро уже что-то да прояснилось, то теперь первое слагаемое должно быть освобождено от битов, по которым перенос учтен:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Как известно, побитовый оператор «Исключающее ИЛИ» выставит биты только если значения разрядов противоположны.
Третий шаг цикла — это преобразование «флагов» наличия переноса непосредственно в перенос. Для этого они сдвигаются на один шаг влево и присваиваются второму слагаемому:
addend = (carry << 1);
0110 = (0011 << 1);
На последующей итерации перенос зафиксирован не будет, т.к:
carry = (summand & addend);
0000 = 0000 & 0110
Второй шаг даст нам:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Что является искомой суммой, а третий шаг завершит цикл while ():
addend = (carry << 1);
0000 = (0000 << 1)
Вычитание
Алгоритм:
private int sub(int minuend, int subtrahend)
{
/*Отрицательный перенос.*/
int borrow = 0x00;
/*Итерировать до тех пор, пока не закончится перенос на младший разряд.*/
while(subtrahend != 0x00)
{
/*Выставить флаг под разрядами с установленными битами.*/
borrow = ((~minuend) & subtrahend);
/*Снять с уменьшаемого биты, разряд по которым уже учтен.*/
minuend = minuend ^ subtrahend;
/*Перенос переводится в старший разряд.*/
subtrahend = (borrow << 1);
}
return minuend;
}
Эквивалентен предыдущему с той лишь разницей, что значение уменьшаемого — это инвертированное слагаемое. Здесь реализовано правило арифметики, согласно которому сложение значений с противоположным знаком дает разность:
a + (-b); (-a) + b;
Таким образом, для реализации побитового вычитания достаточно инвертировать значение первого слагаемого унарным оператором «НЕ» и переименовать локальные переменные.
Умножение
Алгоритм:
public int multiply(int mul1, int mul2)
{
int result = 0;
/*Пока второй множитель не равен нулю.*/
while(mul2 != 0)
{
/*Если установлен бит в очередном разряде...*/
if ((mul2 & 1) == 1)
{
/*сложить первый множитель с самим собою.*/
result = (result + mul1);
}
/*Очередной сдвиг первого множителя влево ("лесенка")*/
mul1 <<= 1;
/*Подводим очередной разряд в начало для сверки с условием оператора if()*/
mul2 >>>= 1;
}
return result;
}
Вернемся к истокам: умножение в столбик в десятичной системе:
25 *
05 =
--
125 +
00
---
125
т.е. мы перемножаем каждый разряд второго множителя с первым множителем. Отсюда же следует, что произведение от старшего разряда сдвигается на один шаг влево. И наконец складываем промежуточные значения. То же самое происходит на побитовом уровне:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Делаем вывод, что алгоритм только и должен, что складывать первый множитель с самим собою всякий раз как во втором множителе встречается установленный бит, естественно, с учетом правила перевода в старший разряд:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = (result + mul1); //0110 = 0000 + 0110
}
Дальше осуществляется сдвиг первого множителя на один разряд влево (формируем «лесенку»):
mul1 <<= 1; //1100 = 0110 << 1;
Теперь определяем, есть ли бит во втором по значимости разряде второго множителя:
mul2 >>>= 1; //0001 = 0011 >>> 1;
Цикл работает до тех пор, пока второй множитель не равен нулю. Хотел бы обратить внимание на следующее: от ресурса к ресурсу гуляет экземпляр этого алгоритма, где логический сдвиг второго множителя (mul2 >>>= 1;) заменен на арифметический (mul2 >>= 1;). Вероятно, он берет свое начало из реализации на C/C++, где есть ключевое слово unsigned и такая подмена не является проблемой. Однако в Java все типы чисел знаковые и если второй множитель будет представлен отрицательным значением, то такая оплошность приведет к вываливанию алгоритма в бесконечный цикл, т.к. второй множитель всегда будет отвечать его условию:
1000 >>1; //пока все хорошо
1100 >>1; //засада замаячила (ожидалось 0100)
1110 >>1; //ожидалось 0010
1111 >>1; // отсюда и далее второй множитель будет иметь значение -1
Деление
Алгоритм:
private int divide(int dividend, int divisor)
{
/*Знак, частное и маска для выставления битов на частном.*/
int quotient = 0x00, mask = 0x01;
/*Для возвращения делителя в исходное состояние.*/
int temp = divisor;
/*Знак отрицательный если только одна переменная отрицательная.*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/*Получить абсолютные значения.*/
dividend = dividend < 0 ? ((~dividend) + 1) : dividend;
divisor = divisor < 0 ? ((~divisor) + 1) : divisor;
/*Вернуть 0 если делимое меньше делителя.*/
if (dividend < divisor) return quotient;
while(dividend > 0)
{
/*Сдвигать влево пока условие истинно.*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/*Граница обнаружена.*/
else
{
/*В переменной "частное" выставить бит.*/
quotient = quotient | mask;
/*Вычесть текущее значение делителя от делимого.*/
dividend = dividend - divisor;
/*Возвращаем делитель и маску в исходное положение.*/
divisor = temp;
mask = 0x01;
}
}
return quotient * sign;
}
С делением вышло не так гладко, как с предыдущими примерами: пришлось писать велосипед (сильно не бить).
Деление — это вычитание делителя от делимого до тех пор, пока частное больше или равно нулю. При таком подходе достаточно определить счетчик, значение которого инкрементируется после каждой операции вычитания. Его итоговое значение и есть частное:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
Недостаток такого подхода становится особенно ощутимым при подаче устройству с ограниченными ресурсами последовательности из инструкций, как то: 2147483647 / 1; 2147483647 / 2; 2147483647 / 3, сложится впечатление, что приложение зависло.
Куда эффективней была бы работа на уровне битов. Но единственное найденное решение имеет тот недостаток, что для корректного вывода требуется тип переменных, на ступень выше охватываемого диапазона, т.е. если на вход подаете short, то тип локальных переменных должен быть int, иначе результат деления больших значений будет удивлять. В моем случае ситуация усугублялась отсутствием типа long.
Но вернемся к нашим баранам.
Для понимания принципа работы алгоритма необходимо вспомнить порядок деления столбиком:
делимое = 6, делитель = 2;
0110|0010
----
110|10 //убираем избыточные биты для лучшего восприятия
Начиная со старшего разряда делимого, пошагово ищем подзначение, которое имеет минимальную разность с делителем:
1) (1 >= 10) -> условие не истинно, записываем ноль в частное
110|10
--
0
2) (11 >= 10) -> условие истинно, записываем единицу в частное
110|10
-11 --
10 01
--
01
Вот тут по-подробней. На выхлопе у нас получилось следующее: мы «вытолкнули» делитель влево до того разряда, где он минимизировал разность с делимым:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> условие истинно, записываем еще одну единицу в частное
110|10
-11 --
10 011
--
-010
010
---
000
Этот механизм реализован в алгоритме. В цикле while () делитель должен сдвигаться влево до тех пор, пока не будет удовлетворять вышеописанному правилу. Параллельно с ним сдвигается маска частного. Оператор ветвления if () гласит: «сдвинуть можно если только результат этой операции не нарушит основное правило». Дополнительная проверка на отрицательное число связана с тем, что в Java выставленный самый старший бит — это отрицательное число. Без него цикл упадет в бесконечность:
//((divisor << 0x01) > 0) если закомментить это условие, то
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - тут if() посчитает, что отрицательный делитель меньше делимого, и будет прав.
4) 0111 >= 0000<<1
....
Как только алгоритм перестал отвечать условиям if (), код входит в else, где на частном устанавливается бит маски:
quotient = quotient | mask;
0010 = 0000 | 0010
Это аналогично выставлению битов при делении столбиком. Затем от делимого вычитается делитель:
dividend = dividend - divisor;
0010 = 0110 - 0100
После этого делитель и маска возвращаются в исходное состояние и цикл начинается вновь:
divisor = temp;
mask = 0x01;
На последок хотел бы добавить несколько слов о дополнительном коде.
Приведенный алгоритм предполагает деление только положительных чисел, которые получены дополнительным кодом:
dividend = dividend < 0 ? ((~dividend) + 1) : dividend;
divisor = divisor < 0 ? ((~divisor) + 1) : divisor;
Тут происходит следующее: если число отрицательное, то его биты инвертируются, а результат складывается с единицей и получаем положительное (абсолютное) значение. Это же правило действительно для положительных чисел, например:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Но есть одно исключение — это максимально большое отрицательное число заданного типа, например:
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
Будьте осторожны.
