Что значит инвертируем все биты числа

Как инвертировать только определённые биты в числе

Мне нужно инвертировать все биты в числе, допустим, 2 ( 10 в двоичной системе) после инвертирования будет равно 01 . Но столкнулся с проблемой, что операция побитового отрицания инвертирует также и знаковый бит и вообще все биты, которыми число представлено в памяти. И получается, что:

Как мне всё-таки получить 1 , а не -3 ?

Вообще-то битовые операции не стоит применять к знаковым целым числам, поэтому я пишу сразу для unsigned .

Увы, из вашего задания мало что понятно. Вы хотите, похоже, инвертировать только биты, начиная со старшего единичного бита?

Здесь для 0 все же инвертируем его в 1.

Но вот не уверен, что вы хотите для 7 или там 3 инвертирование в 0 — все их единички.

О битовых операциях

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

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

• | (Побитовое ИЛИ (OR)),
• & (Побитовое И (AND)),
• ^ (Исключающее ИЛИ (XOR)),

Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

О битовых операторах вам также необходимо знать:

1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
2. Большинство битовых операций являются операциями составного присваивания.

Побитовое ИЛИ (OR)

Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:

38 | 53 будет таким:

A	0	0	1	0	0	1	1	0
B	0	0	1	1	0	1	0	1
A | B	0	0	1	1	0	1	1	1

В итоге мы получаем 110111₂ , или 55₁₀ .

Побитовое И (AND)

Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

A	0	0	1	0	0	1	1	0
B	0	0	1	1	0	1	0	1
A & B	0	0	1	0	0	1	0	0

Как результат, получаем 100100₂ , или 36₁₀ .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

A	1	0	0	0	1	0	1	0
B	0	0	1	0	1	0	1	1
A ^ B	1	0	1	0	0	0	0	1

С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.

Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

Побитовое отрицание (NOT)

Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

Вот, например, операция

Результатом будет 203₁₀

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

Дополнительный код

Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

Например, если мы имеем 109:

Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

Побитовый сдвиг влево

Побитовые сдвиги немного отличаются от рассмотренных ранее битовых операций. Побитовый сдвиг влево сдвигает биты своего операнда на N количество битов влево, начиная с младшего бита. Пустые места после сдвига заполняются нулями. Происходит это так:

A	1	0	1	1	0	1	0	0
A<<2	1	1	0	1	0	0	0	0

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2 N . Таким образом, 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Побитовый сдвиг вправо

Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

Если операнд положительный, то пустые места заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места слева заполняются единицами. Это делается для сохранения знака в соответствии с дополнительным кодом, объясненным ранее.

Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.

Вывод

Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

Битовое представление чисел

Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 ( char ), 16 ( short ), 32 ( int ) или 64 ( long long ) бит.

#Эндианность

Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:

• При схеме little-endian сначала идут младшие биты. Например, число $42_<10>$ будет храниться так: $010101$.
• При записи в формате big-endian сначала идут старшие биты. Все примеры из начала статьи даны в big-endian формате.

Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.

Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.

#Битовые операции

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

#Сдвиги

Битовую запись числа можно «сдвигать» влево ( x << y ) или вправо ( x >> y ), что эквивалентно умножению или делению на степень двойки с округлением вниз.

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

#Побитовые операции

Помимо && , || и ! , существуют их побитовые версии, которые применяют соответствующую логическую операцию к целым последовательностям битов: & , | ,

Также помимо них есть ещё операция исключающего «или» (XOR), которая записывается как ^ .

• $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
• $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
• $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$

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

#Маски

Бинарные последовательности можно поставить в соответствие подмножествам какого-то фиксированного множества: если на $i$-той позиции стоит единица, то значит $i$-тый элемент входит множество, а иначе не входит.

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

#Выделить i-й бит числа

(x >> i) & 1 или x & (1 << i) . Во втором случае результат будет либо 0, либо $2^i$.

Это часто используется для проверки, принадлежит ли $i$-тый элемент множеству:

Напомним, что нумерация идет с младших бит и начинается с нуля.

#Получить число, состоящее из k единиц

(1 << k) — 1 , также известное как $(2^k-1)$ и соответствующее маске полного множества.

#Инвертировать все биты числа

#Добавить i-й элемент в множество

#Удалить $i$-й элемент из множества

#Удалить i-й элемент из множества, если он есть

Также добавляет этот элемент, если его нет.

#Знаковые числа

Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).

Если сложить две unsigned int переменные, сумма которых превосходит $2^<32>$, произойдет переполнение: сумму нельзя будет представить точно, и поэтому вместо неё результатом будут только нижние 32 бит. Все операции с беззнаковыми числами как бы проходят по модулю какой-то степени двойки.

Знаковые же типы нужны для хранения значений, которые могут быть и отрицательными. Для этого нужно выделить один бит для хранение знака — отрицательное ли число или нет — немного пожертвовав верхней границей представимых чисел: теперь самое большое представимое число это $2^<31>-1$, а не $2^<32>-1$.

Инженеры, которые работают над процессорами, ещё более ленивые, чем программисты — это мотивировано не только стремлением к упрощению, но и экономией транзисторов. Поэтому когда в signed типах происходит переполнение, результат в битовом представлении считается так же, как и в случае с unsigned числами. Если мы хотим ничего не менять в плане того, как работают unsigned числа, представление отрицательных чисел должно быть таким, что число $-x$ как бы вычитается из большой степени двойки:

• Все неотрицательные числа записываются в точности как раньше.
• У всех отрицательных чисел самый большой бит будет единичным.
• Если прибавить к $2^<31>-1$ единицу, то результатом будет $-2^<31>$, представляемое как 10000000 (в целях изложения мы будем записывать 8 бит, хотя в int их 32).
• Зная двоичную запись положительного числа x , запись -x можно получить как

Упражнение. Каких чисел больше: положительных или отрицательных?

Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.

#128-битные числа

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

Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.

Базовые арифметические операции с ним чуть медленнее, его нельзя напрямую печатать, и деление и прочие сложные операции будут вызывать отдельную библиотеку и поэтому работать очень долго, однако в некоторых ситуациях он оказывается очень полезен.

JavaScript: заметка о побитовых операторах и числах с плавающей точкой

В этой небольшой заметке я хочу поговорить с вами о манипулировании битами в JavaScript , а также о двоичном представлении чисел с плавающей точкой (floating point numbers).

Обратите внимание: заметка носит, в основном, теоретический характер и направлена на углубленное изучение JavaScript , поэтому предполагается, что вы имеете некоторый опыт работы с данным языком программирования.

С вашего позволения, я не буду рассказывать о двоичной системе счисления и побитовых операторах. О последних хорошо написано здесь.

Начнем с определения функции для вывода в консоль инструментов разработчика в браузере переданного числа в бинарном формате (для типизации параметров и возвращаемого значения я прибегну к помощи TypeScript):

Рассмотрим несколько примеров из этого репозитория.

Функция получения бита

Сначала мы сдвигаем соответствующий бит в нулевую позицию. Затем выполняем операцию & с 1 , которая выглядит как 0001 в двоичном представлении. Это приводит к удалению из числа всех битов, кроме искомого. Если оставшийся бит является 1 , возвращается 1 , иначе возвращается 0 .

Функция установки бита

Сначала мы сдвигаем 1 на количество битов, указанных в bitPosition , создавая значение, похожее на 0010 . Затем выполняем операцию | , которая устанавливает соответствующий бит в значение 1 , но не влияет на другие биты числа.

Функция очистки бита

Сначала мы сдвигаем 1 на количество битов, указанных в bitPosition , создавая значение, похожее на 0010 . Затем инвертируем это значение (обращаем биты на противоположные), получая что-то вроде 1101 . После этого выполняем операцию & над обоими значениями. Это приводит к удалению соответствующего бита.

Функция обновления бита

Это просто сочетание методов clearBit и setBit .

Функция определения четности числа

Здесь весь фокус состоит в том, что крайним правым битом нечетного числа всегда является 1 .

Функция определения положительности числа

Крайним левым (старшим) битом положительного числа всегда является 0 . При этом, для +0 (или просто 0 ) и -0 должно возвращаться false .

Функция умножения числа на 2

Мы сдвигаем все биты числа влево по одному. Это приводит к тому, что все компоненты бинарного числа (степени числа 2 ) умножаются на 2 , поэтому и само число также умножается на 2 .

Функция деления числа на 2

Мы сдвигаем все биты числа вправо по одному. Это приводит к тому, что все компоненты бинарного числа (степени числа 2 ) делятся на 2 , поэтому и само число также делится на 2 .

Функция смены знака числа

Мы инвертируем все биты числа и прибавляем к нему 1 . Данная техника называется «дополнительным кодом» или «дополнением до двух» (two’s complement).

Функция определения количества установленных битов

Основная идея здесь состоит в том, что число сдвигается вправо по одному биту. Результат операции & возвращает либо 1 , либо 0 .

Функция определения количества битов

Мы каждый раз сдвигаем 1 на один бит влево и проверяем, не стало ли «сдвинутое» число больше или равно переданному. В приведенном примере для того, чтобы сдвинутое число стало больше или равно 5 , 1 необходимо сдвинуть 4 раза.

Функция определения того, является ли число степенью числа 2

Предположим, что n — это число, которое является степенью числа 2 (2, 4, 8, 16 и т.д.). Тогда операция & , примененная к n и n — 1 , возвращает 0 :

Функция умножения 2 чисел со знаками

Выражение a * b может быть представлено следующим образом:

• 0 : когда a или b , или a и b равны 0 ;
• 2a * (b/2) : когда b — это четное число;
• 2a * (b-1)/2 + a : когда b — это четное положительное число;
• 2a * (b+1)/2 — a : когда b — это четное отрицательное число.

Преимущество такого подхода состоит в том, что на каждом шаге рекурсии значение одного из операндов уменьшается вдвое. Мы имеем временную сложность O(log b) , поскольку b — это операнд, значение которого уменьшается в 2 раза при каждом рекурсивном вызове функции.

Функция умножения 2 чисел без знаков

В основе этого метода лежит идея о том, что любое число можно представить как сумму степеней числа 2 :

Поэтому умножение числа x на 19 эквивалентно следующему:

А x * 2^4 означает сдвиг x на 4 бита влево ( x << 4 ).

Пожалуй, на этом мы закончим рассмотрение примеров использования побитовых операторов для манипулирования битами чисел.

Что касается практического применения этих операторов в JavaScript , то, кроме приведенных выше функций для определения четности и положительности числа, следует упомянуть о двойном операторе

, который может использоваться как альтернатива методу Math.floor :

А также об одиночном операторе

, с помощью которого можно выполнить проверку на -1 :

Как видите, случаев использования побитовых операторов в JavaScript на так уж и много.

На практике я также встречал побитовые операторы в следующих функциях:

• функция для генерации UUID ( Node.js ):

• функция для получения случайного цвета в формате HEX :

• функция для преобразования цвета из RGB в HEX :

А какие примеры использования побитовых операторов знаете вы? Поделитесь в комментариях.

Теперь поговорим о двоичном представлении чисел с плавающей точкой.

Числа двойной точности в бинарном формате

Вы когда-нибудь задумывались о том, как компьютеры хранят числа с плавающей точкой, такие как 3.1416 (число Пи) или 9.109 × 10⁻³¹ (масса электрона в кг), в памяти, ограниченной определенным количеством нулей и единиц (битов)?

В случае с целыми числами (например, числом 17 ) все достаточно просто. Допустим, у нас есть 16 бит (2 байта) для хранения числа. В 16 битах можно хранить числа в диапазоне [0, 65535] :

Если требуется хранить число со знаком, можно использовать дополнение до двух и сдвинуть диапазон [0, 65535] в отрицательную сторону. В этом случае 16 бит будут представлять числа в диапазоне [-32768, +32768] .

Как можно заметить, такой подход не позволяет хранить числа наподобие -27.15625 (числа после точки будут игнорироваться).

Конечно, мы далеко не первые, кто заметил эту проблему. В далеком 1985 году умные люди преодолели это ограничение, представив стандарт IEEE 754 для чисел с плавающей точкой (далее — стандарт).

Стандарт описывает способ использования 16 бит (или 32, или 64) для хранения чисел более широкого диапазона, включая маленькие числа от 0 до 1.

Для того, чтобы понять идею, лежащую в основе стандарта, следует прибегнуть к экспоненциальной записи (scientific notation) — способу представления чисел, которые являются слишком большими или слишком маленькими (обычно, представленными в виде длинной строки из чисел) для того, чтобы быть пригодными для записи в десятичной форме.

Как видно на изображении, представление числа может быть разделено на 3 части:

• sign — знак;
• fraction (significand) — фракция (значимые числа, полезная нагрузка) числа;
• exponent — экспонента, определяющая, как далеко и в каком направлении сдвигается точка во фракции.

Часть base (основа, система счисления) можно опустить, условившись о том, чему она будет равняться. Мы в качестве основы будет использовать 2 .

Вместо использования всех 16 бит (или 32, или 64) для хранения фракции числа, биты могут быть разделены для хранения знака, экспоненты и фракции по-отдельности. В зависимости от количества битов, имеющихся в нашем распоряжении для хранения числа, получается следующая таблица:

Формат	Общее количество битов	Количество битов для знака	Для экспоненты	Для фракции	Основа
Половинная точность	16	1	5	10	2
Одинарная точность	32	1	8	23	2
Двойная точность	64	1	11	52	2

При таком подходе мы получаем меньшее количество битов для фракции (например, вместо 16 получаем всего 10 ). Это означает, что во фракцию можно записать меньший диапазон чисел (с незначительной потерей точности). Однако, поскольку у нас также имеется часть для экспоненты, на самом деле диапазон чисел расширяется. Это также позволяет описывать числа между 0 и 1 (за счет отрицательной экспоненты).

Например, максимальный значением переменной для 32-битного целого числа является 2³¹ − 1 = 2,147,483,647 , а максимальным значением переменной для 32-битных чисел с плавающей точкой с основанием 2 по стандарту является ≈ 3.4028235 × 10³⁸ .

Для представления отрицательной экспоненты в стандарте используется смещение экспоненты (exponent bias) — вычитание смещения (bias) из экспоненты. Например, если экспонента имеет 5 бит, она может принимать значения в диапазоне [0, 31] (в данном случае все значения положительные). Но если мы вычтем из нее 15 , то диапазон будет выглядеть как [-15, 16] . Число 15 называется смещением и рассчитывается по следующей формуле:

На представленном ниже изображении описывается логика преобразования чисел с плавающей точкой в бинарном формате в десятичный формат. Для простоты используется 16-битное число, но точно такой же подход применяется в отношении 32 и 64-битных чисел:

В этой статье можно найти интерактивную версию приведенного изображения.

В следующей таблице представлены диапазоны, поддерживаемые разными форматами:

Формат	Минимальная экспонента	Максимальная экспонента	Диапазон	Минимальное положительное число
Половинная точность	-14	+15	±65,504	6.10 × 10⁻⁵
Одинарная точность	-126	+127	±3.4028235 × 10³⁸	1.18 × 10⁻³⁸

Обратите внимание: в данной заметке представлен лишь краткий обзор стандарта. Существует несколько крайних случаев, которые обрабатываются в особом порядке. Речь идет о таких значениях, как -0 , -Infinity , +Infinity и NaN .

Примеры кода

— функция для преобразования массива битов в число с плавающей точкой; — функция для преобразования числа с плавающей точкой в двоичное представление согласно стандарту.

Полезные ссылки

Пожалуй, это все, чем я хотел поделиться с вами в данной заметке. Надеюсь, вы нашли для себя что-то интересное и не зря потратили время.