Bitwise что это

Bitwise — обучающий проект по созданию программного и аппаратного стека компьютера с нуля

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

В 2017 году, Per Vognsen — программист с более чем 15-летним стажем, работавший в таких компаниях как NVIDIA и Oculus берет паузу и в марте 2018 стартует амбициозный обучающий проект Bitwise, в котором он собирается разработать и написать весь программно-аппаратный стек для простого компьютера с нуля и запустить его на FPGA.

Проект должен был включать в себя операционную систему, компилятор, системные библиотеки, а также HDL код для центрального процессора и периферийных контроллеров. Пререквизиты к нему минимальны — свободное владение языком Cи (и немного Python), а также знание некоторых алгоритмов и структур данных из стандартных CS курсов. Все остальное объясняется по ходу написания кода.

Проекты подобные Bitwise можно пересчитать по пальцам (думаю многие еще вспомнят о знаменитом Handmade Hero от Casey Muratori). Автором данного проекта выступает отличный программист, который в формате скринкастов показывает и объясняет каждое решение по ходу написания кода. Этой короткой статьей я бы хотел заполнить пробел и познакомить большее число людей с проектом Bitwise, так как сам извлек из него много нового.

Для общего обзора я постарался условно разбить содержание на 5 логических частей:

1. Проект начинается с написания Си-подобного системного языка программирования Ion, который будет использоваться для дальнейшей разработки. Автор приводит аргументы в пользу того, почему он принял решения писать компилятор для нового языка, а не просто использовать Си. Разработка Ion выполняется на чистом C99, без использования сторонних библиотек. Написанный компилятор на выходе генерирует Си код, который затем компилируется стандартным компилятором языка Си. Вся дальнейшая разработка производится на языке Ion.

2. Во второй части автор приступает к написанию ассемблера и эмулятора процессора на базе архитектуры RISC-V и подробно разбирая документацию и систему команд.

3. В третьей части следует написание одной из версий языка программирования Forth на разработанном прежде ассемблере.

4. В четвертой части он переключается на Python и пишет прототип собственного DSL для разработки аппаратной части.

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

К сожалению на данный момент проект не активен. В первый раз большая пауза произошла спустя несколько месяцев после запуска, а через некоторое время автор вернулся и обещал продолжать проект. Однако это продлилось недолго, так как по его последнему посту на github, мы узнаем, что он сильно выгорел и пока не хочет давать никаких обещаний насчет продолжения. Но в любом случае, то что уже было сделано, а это более 100 часов видео, я считаю заслуживающим внимания:

Весь код с историей можно найти по ссылке, а видео доступны на канале https://www.youtube.com/pervognsen

Видео материал разделен на 2 плейлиста (основной и экстра, в котором некоторые моменты рассматриваются более подробно):

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

Перевод «bitwise» на русский

The usual arithmetic conversions are performed; the result is the bitwise AND function of the operands.

Выполняются обычные арифметические преобразования; результат — побитовое И операндов.

To determine the boundaries of the subnet, the computer does a bitwise multiplication (logical AND) between the IP address and the mask, getting the output address with zero bits in the mask zero positions.

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

An integer expression that specifies bitwise file attributes.
Любое целое выражение, указывающее побитовые атрибуты файла.
The player can modify values of bits by applying the bitwise logical operations And, Or and Xor.

Игрок может модифицировать значения битов, локально применяя побитовые логические операции And, Or и Xor.

The structure of connections between basic cells, delay indicators and the number of bitwise shift operations in cells are described by row vectors.

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

There is a sign mismatch for the bitwise binary operands for this operator must be both positive or both negative.

Несогласованность знаков для побитового бинарного оператора. Оба операнда этого оператора должны быть либо положительными, либо отрицательными.

The first addition (One’s complement), in which we perform a bitwise no operation for a number, to make it negative.

Первое дополнение (One«s complement), в котором мы выполняем операцию побитового нет для числа, чтобы сделать его отрицательным.

The basic examples of breaking this rule would be writing a separate function only to conduct addition operation, or using a bitwise operator (right shift»1) to divide integers by 2.

В качестве примеров нарушения этого принципа можно назвать написание отдельной функции только лишь для осуществления операции сложения или использование побитового оператора (right shift»1) для деления целых чисел на 2.

There are a lot of efficiencies to be gained through bit manipulation, and bitwise operations on a 64-bit word go a lot further than on a 32-bit word.

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

First, we have the bitwise AND (&) operator.
Для начала рассмотрим действие оператора побитового И (&)

It defines a number of macros which allow programmers to use C language bitwise and logical operators, which, without the header file, cannot be quickly or easily typed on some international and non-QWERTY keyboards.

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

Unlike common logical operators (like +, -, ), which work with bytes or groups of bytes, bitwise operators can check or set each of the individual bits within a byte.

В отличие от обычных логических операторов (например,+, -, ), которые работают с байтов или групп байтов, побитовые операторы вы можете проверить или установить отдельные биты в байте.

The compound bitwise AND operator&= is often used with a variable and a constant to force particular bits in a variable to the LOW state (to 0).

Оператор составного побитового И (&=) часто употребляется между переменной и константой чтобы перевести отдельные биты переменной в низкий уровень (0).

There is a somewhat unusual operator in C++ called bitwise exclusive OR, also known as bitwise XOR.

Существует несколько необычный оператор в С называются побитовое исключающее ИЛИ, также известный как побитовое XOR. (логическое И).

The basic premise is that if two corresponding bits are the same, then a bitwise AND operation will return 1, while if they are different, a bitwise AND operation will return 0.

Основной предпосылкой является то, что если две соответствующие бита одинаковы, то побитовое И будет возвращать 1, в то время как, если они различны, побитовое операция И вернет 0.

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

Побитовые операторы интерпретируют операнды как последовательность из 32 битов (нулей и единиц). Они производят операции, используя двоичное представление числа, и возвращают новую последовательность из 32 бит (число) в качестве результата.

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

Формат 32-битного целого числа со знаком

Побитовые операторы в JavaScript работают с 32-битными целыми числами в их двоичном представлении.

Это представление называется «32-битное целое со знаком, старшим битом слева и дополнением до двойки».

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

• Что такое двоичная система счисления, вам, надеюсь, уже известно. При разборе побитовых операций мы будем обсуждать именно двоичное представление чисел, из 32 бит.
• Старший бит слева – это научное название для самого обычного порядка записи цифр (от большего разряда к меньшему). При этом, если больший разряд отсутствует, то соответствующий бит равен нулю. Примеры представления чисел в двоичной системе:

a = 0; // 00000000000000000000000000000000 a = 1; // 00000000000000000000000000000001 a = 2; // 00000000000000000000000000000010 a = 3; // 00000000000000000000000000000011 a = 255;// 00000000000000000000000011111111

00000000000000000000000100111010

Чтобы получить -314 , первый шаг – обратить биты числа: заменить 0 на 1 , а 1 на 0 :

11111111111111111111111011000101

Второй шаг – к полученному двоичному числу прибавить единицу, обычным двоичным сложением: 11111111111111111111111011000101 + 1 = 11111111111111111111111011000110 . Итак, мы получили:

-314 = 11111111111111111111111011000110

Список операторов

В следующей таблице перечислены все побитовые операторы. Далее операторы разобраны более подробно.

Оператор	Использование	Описание
Побитовое И (AND)	a & b	Ставит 1 на бит результата, для которого соответствующие биты операндов равны 1.
Побитовое ИЛИ (OR)	a | b	Ставит 1 на бит результата, для которого хотя бы один из соответствующих битов операндов равен 1.
Побитовое исключающее ИЛИ (XOR)	a ^ b	Ставит 1 на бит результата, для которого только один из соответствующих битов операндов равен 1 (но не оба).
Побитовое НЕ (NOT)	~a	Заменяет каждый бит операнда на противоположный.
Левый сдвиг	a	Сдвигает двоичное представление a на b битов влево, добавляя справа нули.
Правый сдвиг, переносящий знак	a >> b	Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты.
Правый сдвиг с заполнением нулями	a >>> b	Сдвигает двоичное представление a на b битов вправо, отбрасывая сдвигаемые биты и добавляя нули слева.

Побитовые операторы работают следующим образом:

1. Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
2. Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
3. Получившаяся в результате последовательность бит интерпретируется как обычное число.

Посмотрим, как работают операторы, на примерах.

Вспомогательные функции parseInt, toString

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

• parseInt(«11000», 2) – переводит строку с двоичной записью числа в число.
• n.toString(2) – получает для числа n запись в 2-ной системе в виде строки.

let access = parseInt("11000", 2); // получаем число из строки alert( access ); // 24, число с таким 2-ным представлением let access2 = access.toString(2); // обратно двоичную строку из числа alert( access2 ); // 11000

Без них перевод в двоичную систему и обратно был бы куда менее удобен. Более подробно они разбираются в главе Числа.

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

Выполняет операцию И над каждой парой бит.

Результат a & b равен единице только когда оба бита a и b равны единице.

Таблица истинности для & :

a	b	a & b
0	0	0
0	1	0
1	0	0
1	1	1

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 & 9 (по осн. 10) = 00000000000000000000000000001000 (по осн. 2) = 8 (по осн. 10)

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

Выполняет операцию ИЛИ над каждой парой бит. Результат a | b равен 1, если хотя бы один бит из a,b равен 1.

Таблица истинности для | :

a	b	a | b
0	0	0
0	1	1
1	0	1
1	1	1

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 | 9 (по осн. 10) = 00000000000000000000000000001111 (по осн. 2) = 15 (по осн. 10)

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

Выполняет операцию «Исключающее ИЛИ» над каждой парой бит.

a Исключающее ИЛИ b равно 1, если только a=1 или только b=1 , но не оба одновременно a=b=1 .

Таблица истинности для исключающего ИЛИ:

a	b	a ^ b
0	0	0
0	1	1
1	0	1
1	1	0

Как видно, оно даёт 1, если ЛИБО слева 1 , ЛИБО справа 1 , но не одновременно. Поэтому его и называют «исключающее ИЛИ».

9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) 14 (по осн. 10) = 00000000000000000000000000001110 (по осн. 2) -------------------------------- 14 ^ 9 (по осн. 10) = 00000000000000000000000000000111 (по осн. 2) = 7 (по осн. 10)

Исключающее ИЛИ в шифровании

Исключающее или можно использовать для шифрования, так как эта операция полностью обратима. Двойное применение исключающего ИЛИ с тем же аргументом даёт исходное число.

Иначе говоря, верна формула: a ^ b ^ b == a .

Пусть Вася хочет передать Пете секретную информацию data . Эта информация заранее превращена в число, например строка интерпретируется как последовательность кодов символов.

Вася и Петя заранее договариваются о числовом ключе шифрования key .

• Вася берёт двоичное представление data и делает операцию data ^ key . При необходимости data бьётся на части, равные по длине key , чтобы можно было провести побитовое ИЛИ ^ для каждой части. В JavaScript оператор ^ работает с 32-битными целыми числами, так что data нужно разбить на последовательность таких чисел.
• Результат data ^ key отправляется Пете, это шифровка.

Например, пусть в data очередное число равно 9 , а ключ key равен 1220461917 .

Данные: 9 в двоичном виде 00000000000000000000000000001001 Ключ: 1220461917 в двоичном виде 01001000101111101100010101011101 Результат операции 9 ^ key: 01001000101111101100010101010100 Результат в 10-ной системе (шифровка): 1220461908

• Петя, получив очередное число шифровки 1220461908 , применяет к нему такую же операцию ^ key .
• Результатом будет исходное число data .

Полученная шифровка в двоичной системе: 9 ^ key = 1220461908 01001000101111101100010101010100 Ключ: 1220461917 в двоичном виде: 01001000101111101100010101011101 Результат операции 1220461917 ^ key: 00000000000000000000000000001001 Результат в 10-ной системе (исходное сообщение): 9

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

~ (Побитовое НЕ)

Производит операцию НЕ над каждым битом, заменяя его на обратный ему.

Таблица истинности для НЕ:

a	~a
0	1
1	0

 9 (по осн. 10) = 00000000000000000000000000001001 (по осн. 2) -------------------------------- ~9 (по осн. 10) = 11111111111111111111111111110110 (по осн. 2) = -10 (по осн. 10)

Из-за внутреннего представления отрицательных чисел получается так, что ~n == -(n+1) .

Bitwise AND (&)

Побитовый оператор И ( & ) возвращает 1 в каждой битовой позиции, для которой соответствующие биты обоих операндов равны 1 .

Интерактивный пример

Синтаксис

a & b

Описание

Операнды преобразуются в 32-битные целые числа и выражаются серией битов (нулей and единиц). Числа с более чем 32 битами отбрасывают старшие разряды. Например, следующее целое число с более чем 32 битами будет преобразовано в 32-битное целое:

До: 11100110111110100000000000000110000000000001 После: 10100000000000000110000000000001

Каждый бит в первом операнде связан с соответствующим битом во втором операнде:первый бит — с первым,второй- со вторым, и т.д.

Оператор применяется к каждой паре битов, и результат строится побитово.

Таблица истинности для оператора И:

a	b	a И b
0	0	0
0	1	0
1	0	0
1	1	1

. 9 (base 10) = 00000000000000000000000000001001 (base 2) 14 (base 10) = 00000000000000000000000000001110 (base 2) -------------------------------- 14 & 9 (base 10) = 00000000000000000000000000001000 (base 2) = 8 (base 10) 

Побитовое И для любого числа x с 0 даёт 0 .

Примеры

Использование побитового И

// 5: 00000000000000000000000000000101 // 2: 00000000000000000000000000000010 5 & 2; // 0 

Спецификации

Specification
ECMAScript Language Specification # prod-BitwiseANDExpression

Браузерная совместимость

BCD tables only load in the browser

Смотрите также

• Bitwise operators in the JS guide
• Bitwise AND assignment operator (en-US)

Found a content problem with this page?

• Edit the page on GitHub.
• Report the content issue.
• View the source on GitHub.

This page was last modified on 7 авг. 2023 г. by MDN contributors.

Your blueprint for a better internet.

MDN

Support

• Product help
• Report an issue

Our communities

Developers

• Web Technologies
• Learn Web Development
• MDN Plus
• Hacks Blog

• Website Privacy Notice
• Cookies
• Legal
• Community Participation Guidelines

Visit Mozilla Corporation’s not-for-profit parent, the Mozilla Foundation.
Portions of this content are ©1998– 2023 by individual mozilla.org contributors. Content available under a Creative Commons license.