Побитовое отрицание — почему так

Побитовое отрицание ~ в Java инвертирует все 32 бита переменной int, а не только значащие. Число 342 хранится как 00000000000000000000000101010110, после инверсии получается 11111111111111111111111010101001, а это в дополнительном коде уже -343, потому что старший бит стал единицей и означает минус. Общее правило: ~x всегда равно -x - 1 (JLS, раздел 15.15.5). Ниже разберем, откуда берется 169, как устроен знаковый разряд и как посчитать -343 вручную.

Кратко

• ~342 в Java равно -343, а не 169: инверсия действует на все 32 бита int, включая ведущие нули.
• Все целые типы Java (byte, short, int, long) хранятся в дополнительном коде; старший бит это знаковый разряд.
• Числа с 0 в старшем бите положительные (от 0 до 2147483647), с 1 отрицательные (от -2147483648 до -1).
• Вес старшего бита не +2^31, а -2^31: -343 = -2147483648 + 2147483305.
• Формула из спецификации: ~x == -x - 1, поэтому ~0 == -1, а ~(-1) == 0.
• Проверить все это можно кодом: Integer.toBinaryString(~342) печатает все 32 бита, а разобрать такую строку обратно поможет Integer.parseUnsignedInt(s, 2).

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

Почему конвертер показывает 169

У особо пытливых (таких, как я) возник вопрос: "эй, но ведь 010101001 меньше, чем 101010110, логично, что оно должно быть меньше 342 и положительным". Вбивая в любом онлайн-конвертере чисел или же проверяя это с помощью кода:

Integer a = Integer.valueOf("010101001", 2);
System.out.println(Integer.toString(a, 10));

неожиданно получаем совсем не -343... Эх, как же хорошо, что когда-то давно на парах по программированию на C я как-то мельком услышал что-то про знаковый разряд в целых числах. Какое-то время погуглив, теперь я могу пояснить, что это за зверь.

int хранит 32 бита, а не девять

На самом деле в той версии статьи была неточность, которая и ставила в тупик. Если мы проверим при помощи кода, что же действительно является результатом инверсии числа 342:

int a = 342;
System.out.println(Integer.toBinaryString(~a));

то увидим немного другой результат Почему же так? Все дело в том, что в переменной не может лежать просто 101010110, на самом деле оно хранится как Ведь переменная типа int занимает 4 байта, т.е. 32 бита, 32 ячейки памяти (спецификация прямо говорит, что все целые типы Java хранятся как знаковые числа в дополнительном коде: JLS, раздел 4.2.1). После инверсии меняются абсолютно все цифры, т.е. и "обрезанные" в начале нули.

Знаковый разряд: как int хранит отрицательные числа

А теперь самое интересное. Так как в бинарном представлении знак + или - перед числом сохранить не получается, то существует одна хитрость: самый первый (старший) бит на самом деле отвечает за знак и как раз является тем самым знаковым разрядом. А все числа хранятся по такой логике: числа от 00...000 до 01...111 положительные, начинающиеся с 0 (т.е. от 0 до 2147483647) а начиная с 10...000 до 11...111 это отрицательные, начиная с самого минимального и заканчивая -1 (т.е. от -2147483648 до -1).

00000000000000000000000000000000 = 0
01111111111111111111111111111111 = 2147483647
10000000000000000000000000000000 = -2147483648
11111111111111111111111111111111 = -1

И дальше вы спросите "Хорошо, Шерлок, поверим тебе, но откуда ты знаешь, что Ватсон был в Афганистане" но как же при всем этом получается -343?

Считаем -343 вручную

Все на самом деле просто. Мы можем это просто посчитать вручную. Если мы от двоичной версии получившегося после инверсии числа 342 (11111111111111111111111010101001) "отрежем" (или заменим на 0) самый первый бит и вернем его обратно в десятичную форму.

String s = "01111111111111111111111010101001";
System.out.println(s + " = " + Integer.toString(Integer.valueOf(s, 2), 10));

то получим, что На самом же деле здесь мы не просто "отрезали" 1 в начале, а вычли из этого числа 10000000000000000000000000000000. Теперь прибавим его обратно, но уже в десятичном виде. Что мы увидим:

~342 =
11111111111111111111111010101001 =
//в двоичном виде//
01111111111111111111111010101001 +
10000000000000000000000000000000
=
//в десятичном виде//
-2147483648 + 2147483305 = -343

Вот и искомое число -343 :) Общее правило, которое прячется за этим расчетом, записано прямо в спецификации: ~x всегда равно -x - 1 (JLS, раздел 15.15.5). Поэтому ~342 == -343, ~0 == -1, а ~(-1) == 0. Обратная формула тоже полезна: -x == ~x + 1, именно так процессор получает отрицательное число из положительного. Ребят, это мой первый пост тут, поставьте, пожалуйста, ему лайк, если понравилось и было познавательно (очень уж я хочу собрать все достижения 😄) Более подробно по этой теме, можно почитать вот тут:

• Целое (тип данных)
• Дополнительный код

Всем удачи и спасибо за внимание)

Вопросы и ответы

Почему ~342 в Java равно -343, а не 169?

Потому что ~ инвертирует все 32 бита переменной int, а не только девять значащих. 342 хранится как 00000000000000000000000101010110; после инверсии ведущие нули становятся единицами: 11111111111111111111111010101001. Старший бит равен 1, значит число отрицательное, и в дополнительном коде это -343. Число 169 получается, только если инвертировать девять бит и забыть про остальные 23.

Что такое знаковый разряд?

Старший (самый левый) бит целого числа. Если он 0, число неотрицательное (для int от 0 до 2147483647), если 1, отрицательное (от -2147483648 до -1). Отдельного знака «минус» в памяти нет: знак закодирован в этом бите, а его вес в дополнительном коде равен -2^31, а не +2^31.

Что такое дополнительный код (two's complement)?

Способ хранения целых чисел со знаком, который используют все целые типы Java: byte, short, int и long (JLS 4.2.1). Значение читается как обычная двоичная запись, но старший бит берется со знаком минус: для int это -2^31. Чтобы получить -x, нужно инвертировать все биты x и прибавить 1. Плюс подхода: сложение и вычитание работают одинаково для положительных и отрицательных чисел, а ноль представлен единственным образом.

Чему равно ~x для любого числа?

-x - 1, и это гарантирует спецификация (JLS 15.15.5). ~342 равно -343, ~0 равно -1, ~(-1) равно 0, ~Integer.MAX_VALUE равно Integer.MIN_VALUE. Для long правило то же, только битов 64. Обратная формула: -x == ~x + 1.

Как увидеть двоичное представление отрицательного числа в Java?

Через Integer.toBinaryString(x): метод печатает все 32 бита без знака, для -343 это 11111111111111111111111010101001, а у положительных чисел ведущие нули опускаются. Для long есть Long.toBinaryString. byte и short перед вызовом приводятся к int, поэтому у (byte) -1 будет 32 единицы, а не 8.

Почему Integer.parseInt("11111111111111111111111010101001", 2) бросает исключение?

parseInt ожидает знаковое число: без минуса впереди такая строка означает 4294966953, а это больше Integer.MAX_VALUE, поэтому NumberFormatException. Чтобы разобрать 32-битную запись как есть, используйте Integer.parseUnsignedInt(s, 2) (есть с Java 8): он вернет -343.

Читайте также

• Операции над числами в Java
• Устройство вещественных чисел
• Обертки, распаковка и запаковка