Побитовая арифметика в 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;
}

Эквивалентен предыдущему с той лишь разницей, что заем битов у старших разрядов реализован инверсия обратной импликации. Ну и переименовываем локальные переменные.

Умножение


Алгоритм:

public int multiply(int mul1, int mul2)
{
	int result = 0;
	/*Пока второй множитель не равен нулю.*/
	while(mul2 != 0)
	{
		/*Если установлен бит в очередном разряде...*/
		if ((mul2 & 1) == 1)
		{
			/*сложить первый множитель с самим собою.*/
			result = add(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 = add(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 ? add((~dividend), 1) : dividend;
	divisor		= divisor	< 0 ? add((~divisor), 1) : divisor;
	
	/*Вернуть 0 если делимое меньше делителя.*/
	if (dividend < divisor) return quotient;

	while(dividend > 0 || divisor != 0)
	{
		/*Сдвигать влево пока условие истинно.*/
		if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
		{
			divisor	<<= 0x01;
			mask	<<= 0x01;
		}
		/*Граница обнаружена.*/
		else
		{
			/*В переменной "частное" выставить бит.*/
			quotient = quotient | mask;
			/*Вычесть текущее значение делителя от делимого.*/
			dividend = sub(dividend, divisor);
			/*Возвращаем делитель и маску в исходное положение.*/
			divisor	= temp;
			mask	= 0x01;
		}
	}
	return multiply(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
-10  --
 --  01
 01


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

2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.

3) (10 >= 10) -> условие истинно, записываем еще одну единицу в частное
 110|10
-10  --
 --  011
 010
 -10
  --
  00

Этот механизм реализован в алгоритме. В цикле 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 = sub(dividend, divisor);
0010 = 0110 - 0100

После этого делитель и маска возвращаются в исходное состояние и цикл начинается вновь:

divisor	= temp;
mask	= 0x01;

Напоследок хотел бы добавить несколько слов о дополнительном коде.

Приведенный алгоритм предполагает деление только положительных чисел, которые получены дополнительным кодом:

dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~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.

Будьте осторожны.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 23

    0
    В вычитании для дополнительного кода -x = not x +1. not вижу а +1 не видно.
      0
      Предполагается только инверсия, но не дополнительный код, иначе работать не будет.
        0
        Я вас не понял. У вас алгоритм сложения и вычитания одинаковые. Одинаковый алгоритм возможен только для чисел в дополнительном коде. В вычитании вы теряете +1, и сейчас, насколько я понимаю, результат неправильный даже для положительных чисел.
          0
          Они практически одинаковые, разница лишь в инверсии.
          m = 3
          0011
          s = 2
          0010
          
          b	=~m & s
          0000 = 1100 & 0010
          
          m	= m ^ s
          0001 = 0011 ^ 0010
          
          s	= b << 1
          0000 = 0000 << 0001
          
          return m (0001)
          

          Приношу извинения, что не раскрыл этот абзац в статье.
            0
            Спасибо. Я разобрался. У вас классическое побитовое вычитание.
            ЗЫ Лучше убрать упоминание про вычитание, как сложение с отрицательным знаком. Это к вашему алгоритму никакого отношения не имеет вообще. Меня это полностью запутало.
            ЗЫЗЫ Лучше написать что перенос при сложении, это когда биты одинаковые, а заем при вычитании это когда инверися обратной импликации.
              0
              Понял, благодарю, удаляю!)
                0
                Все таки стоит упомянуть что заем это инверсированая обратная
                импликация.
                Она действительно вычисляется как ((not a) and b). Поэтому здесь not — часть вычисления импликации, и отдельного смысла в нем нет.
                  0
                  Исправил)
      +9
      зачем это все?
        +1
        Ну, битовые операции сами по себе весьма фундаментальная вещь.
          0
          Ну, например, может пригодиться для обфускации кода каких-нибудь алгоритмов защиты
          0

          Нда. Начнем со сложения. Почему на входе два аргумента и на выходе один результат?
          Собственно вот тут: https://m.habr.com/ru/post/455312/
          расписана правильная реализация однобитного сумматора, у нее на входе: три аргумента: два слагаемых и бит переноса, на выходе два результата: сумма и перенос.

            +2
            Потому, что это программная реализация, а не аппаратная.
              +1

              Неважно какая реализация. Суть однобитного сумматора в том что его можно каскадировать и обрабатывать N битные числа. Каскадирование в вашей реализации — невозможно, отсюда вопрос накой она нужна?

                +1
                Еще как важно.
                Вы предлагаете подавать на вход три аргумента, получать на выходе два. Вы часто имеете дело с таким калькулятором?

                Еще раз для «внимательных»: задача — побитовый АНАЛОГ арифметических операций, а не СУММАТОР.
                Нужно было бы реализовать схему из вашей ссылки, то поверьте, я бы этим и занялся.
                Эти алгоритмы прекрасно работает с заданными диапазонами, достаточно указать цлевой тип.
                Прежде чем вывалить здесь свое безапелляционное «фи», для приличия, хотя бы, копи-пастнице исхоник.
                  –1
                  Вы часто имеете дело с таким калькулятором?

                  Постоянно. Оно на уровне регистров АЛУ именно так и работает.


                  Еще раз для «внимательных»: задача — побитовый АНАЛОГ арифметических операций …

                  Только два бита складывать? и зачем такой калькулятор нужен?

            0

            Алгоритм умножения у вас с ошибкой. При умножение чисел больше чем INT_MAX /2 значащие биты при сдвиге mul1 будут теряться. Надо было сначала перевести в long.
            И ещё — это только умножение неотрицательных чисел. Отрицательные умножаются по другому.

              0
              Отнюдь.
              Для проверки откройте стандартный калькулятор Windows, установите размер слова в DWORD (эквивалентно 32 битам) и умножение 2147483647 * 2 = -2; да, по причине целочисленного переполнения, но в статье я указывал, что у меня нет long (работа с устройствами с ограниченными ресурсами).

              Умножение отрицательных значений проверено, отточено, выстрадано)
              Вероятно, вы его спутали с тем, в котором while(mul2 > 0) — там да, необходимо получение абсолютных значений и сохранение знака, а инструкция возвращения будет выглядеть так: return result * sign;
              0
              Есть очень хорошая книжка по алгоритмам — Злобин В. К., Григорьев В. Л. — Программирование арифметических операций в микропроцессорах.
              Кстати, насколько я поримаю, деление и умножение побитовые очень медленные. В железе тоже используют алгоритмы с таблицами а не с битами.
                0
                Благодарю за рекомендацию, обязательно ознакомлюсь с этим трудом! Просто моя задача была не в программировании микропроцессора, а проверка на корректность работы заложенных в него арифметических операций.
                +1
                есть одно исключение — это максимально большое отрицательное число заданного типа

                Вот-вот. До сих пор раздражает что в Java не завезли unsigned…

                  +1
                  subtrahend

                  А что было не так с subtract, что пришлось наделить переменную настолько интимным корнем, что я его даже обратно на русский и перевести-то стесняюсь?

                    +1
                    :)
                    У меня нет достаточных познаний в английском, особенно в арифметической терминологии, потому, на всякий случай, я сверялся с multitran.com, согласно которому:
                    minuend — уменьшаемое;
                    subtrahend — вычитаемое;
                    subtract — гл. вычитать;

                  Only users with full accounts can post comments. Log in, please.