Bitwise что это
Перейти к содержимому

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 плейлиста (основной и экстра, в котором некоторые моменты рассматриваются более подробно):

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

Побитовый оператор AND: &

Побитовый оператор AND ( & ) сравнивает каждый бит первого операнда с соответствующим битом второго операнда. Если оба бита равны 1, соответствующий бит результата равен 1. В противном случае соответствующий бит результата равен 0.

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

Оператор ключевое слово для &

C++ указывает bitand в качестве альтернативной орфографии для & . В C альтернативная орфография предоставляется в виде макроса в заголовке . В C++альтернативная орфография является ключевое слово; или эквивалентное не рекомендуется. В Microsoft C++ /permissive- параметр или /Za компилятор требуется для включения альтернативной орфографии.

Пример

// expre_Bitwise_AND_Operator.cpp // compile with: /EHsc // Demonstrate bitwise AND #include using namespace std; int main() < unsigned short a = 0xCCCC; // pattern 1100 . unsigned short b = 0xAAAA; // pattern 1010 . cout 

Как переводится на русский слово «bitwise»?

Fair queuing selects transmission order for the packets by modeling finish time for each packet as if they could be transmitted bitwise round robin.

  • open_in_new Ссылка на источник
  • warning Запрос проверить

The validator can have custom project code to do fuzzy comparison between results, or it can be just a bitwise comparison.

  • open_in_new Ссылка на источник
  • warning Запрос проверить

The two colors may also be combined in more complex ways, e.g. by computing their bitwise exclusive or.

  • open_in_new Ссылка на источник
  • warning Запрос проверить

Next, the results from each index are combined into the bitmap using bitwise operations.

  • open_in_new Ссылка на источник
  • warning Запрос проверить

The source and destination pegs for the "m" th move can also be found elegantly from the binary representation of "m" using bitwise operations.

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

Существует несколько побитовых операторов, применимых к целочисленными типам long, int, short, char, byte.

~ Побитовый унарный оператор NOT
& Побитовый AND
&= Побитовый AND с присваиванием
| Побитовый OR
|= Побитовый OR с присваиванием
^ Побитовый исключающее OR
^= Побитовый исключающее OR с присваиванием
>> Сдвиг вправо
>>= Сдвиг вправо с присваиванием
>>> Сдвиг вправо с заполнением нулями
>>= Сдвиг вправо с заполнением нулями с присваиванием

Все целочисленные типы представляются двоичными числами различной длины. Например, значение типа byte, равное 42, в двоичном представлении имеет вид 00101010, в котором каждая позиция представляет степень числа два.

Все целочисленные типа, за исключением char - типы со знаком, т.е. могут быть положительными или отрицательными. В Java применяется двоичное дополнение, при котором отрицательные числа представляются в результате инвертирования всех битов значения (изменения 1 на 0 и наоборот) и последующего добавления 1 к результату. Например, -42 представляется в результате инвертирования всех битов в двоичном представлении числа 42, что даёт значение 11010101, и добавления 1, что приводит к значению 110110110, или -42. Чтобы декодировать отрицательное число, необходимо вначале инвертировать все биты, а затем добавить 1 к результату. Например, инвертирование значения -42, или 11010110, приводит к значению 00101001, или 41, после добавления 1 к которому мы получим 42.

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

Побитовые логические операторы

Побитовые логические операторы - это &, |, ^, ~. Побитовые операторы применяются к каждому отдельному биту каждого операнда.

Результаты выполнения побитовых логических операторов

A B A | B A & B A ^ B ~A
0 0 0 0 0 1
1 0 1 0 1 0
0 1 1 0 1 1
1 1 1 1 0 0

Побитовое OR (|)

Результирующий бит, полученный в результате выполнения оператора OR, |, равен 1, если соответствующий бит в любом из операндов равен 1.

00101010 42 | 00001111 15 -------------- 00101111 47

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

Значение бита, полученное в результате выполнения побитового оператора AND, &, равно 1, если соответствующие биты в операндах также равны 1. Во всех остальных случаях значение результирующего бита равно 0.

00101010 42 & 00001111 15 -------------- 00001010 10

Побитовое XOR (^)

Результирующий бит, полученный в результате выполнения оператора XOR, ^, равен 1, если соответствующий бит только в одном из операндов равен 1. Во всех других случаях результирующий бит равен 0.

00101010 42 ^ 00001111 15 -------------- 00100101 37

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

 int x = 5, y = 7; x = x ^ y; // стало 2 System.out.println(x); y = x ^ y; // стало 5 System.out.println(y); x = x ^ y; //стало 7 System.out.println(x); 

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

Гораздо шире используется XOR для шифрования. В простейшем виде это выглядит так. Есть текст, к которому применяется ключ с оператором XOR. Зашифрованное сообщение передаётся человеку, который знает ключ. Всё, что ему нужно сделать - это применить к зашифрованному тексту тот же ключ, используемый для шифровки и текст снова станет читаемым.

Ниже приводится приблизительный пример работы шифровки/дешифровки текста. С русским текстом пример не будет работать, так как используются разные кодировки и требуется писать дополнительный код. Итак, у нас есть некий текст, который мы зашифровали с помощью ключа (meow) и передали полученный набор байтов другому человеку. Если кто-то перехватит ваше сообщение, то увидит просто набор символов. А ваш сообщник сможет прочитать сообщение, так как вы заранее условились, каким будем ключ для расшифровки.

 public void onClick(View view) < String message = "OK, i love you"; // секретное сообщение String catkey = "meow"; // ключ // зашифруем послание byte[] important = encode(message, catkey); // посмотрим на результат mInfoTextView.setText(new String(important)); // теперь расшифруем текст mResultEditText.setText(decode(mInfoTextView.getText().toString().getBytes(), catkey)); >// метод для шифровки текста с помощью XOR public static byte[] encode(String secret, String key) < byte[] btxt = null; byte[] bkey = null; btxt = secret.getBytes(); bkey = key.getBytes(); byte[] result = new byte[secret.length()]; for (int i = 0; i < btxt.length; i++) < result[i] = (byte) (btxt[i] ^ bkey[i % bkey.length]); >return result; > // метод для расшифровки текста public static String decode(byte[] secret, String key) < byte[] result = new byte[secret.length]; byte[] bkey = key.getBytes(); for (int i = 0; i < secret.length; i++) < result[i] = (byte) (secret[i] ^ bkey[i % bkey.length]); >return new String(result); > 

Побитовое NOT (~)

Унарный оператор NOT (Не), ~, называемый также побитовым дополнением, инвертирует все биты операнда. Например, число 42 в битовом представлении имеет вид:

00101010

В результате применения оператора NOT преобразуется в значение:

11010101

Сдвиг влево

значение  

Параметр количество указывает, на сколько нужно сдвинуть влево биты в параметре значение. При каждом сдвиге влево самый старший бит смещается за пределы допустимого значения и теряется, а справа дописывается нуль. Это означает, что при применении оператора сдвига влево к операнду типа int биты теряются, как только они сдвигаются за пределы 31 позиции. Если операнд имеет тип long, биты теряются после сдвига за пределы 63 позиции.

Автоматическое повышение типа, используемое в Java, может привести к странным результатам при выполнении сдвига в значениях типа byte, short. При вычислении выражений тип значений byte и short повышается до типа int. Это означает, что результатом выполнения сдвига влево значения типа byte или short будет значение int, и сдвинутые влево позиции не будут отброшены до тех пор, пока они не будут сдвинуты за пределы 31 позиции. Более того, при повышении до типа int отрицательное значение типа byte или short получит дополнительный знаковый разряд. Следовательно, старшие биты будут заполнены единицами. Поэтому выполнение оператора сдвига влево предполагает необходимость отбрасывания старших байтов результата типа int. Иными словами, при выполнении сдвига влево в значении типа byte сначала будет повышение до типа int и лишь затем сдвиг. Это означает, что для получения требуемого сдвинутого значения типа byte необходимо отбросить три старших байта результата. Простейший способ достижения этого - обратное приведение результата к типу byte.

 byte x = 64; byte y; int i; i = x  

Результат будет следующим:

i равно: 256 y равно: 0

Поскольку для выполнения вычислений тип переменной повышается до int, сдвиг влево на две позиции значение 64 (0100 0000) приводит к значению 256 (1 0000 0000). Однако, переменная y содержит значение не 256, а 0, поскольку после сдвига крайний единичный бит оказывается сдвинутым за пределы допустимого диапазона.

Приёмом сдвига влево часто пользуются в программах, где происходит много сложных вычислений. По сути, это замена операции умножения на 2, которая в силу особенностей процессора гораздо эффективнее. При этом следует соблюдать осторожность, так как при сдвиге единичного бита в старшую позицию (бит 31 или 63) значение становится отрицательным.

Сдвиг вправо

Оператор сдвига вправо, >>, смещает все биты значения вправо на указанное количество позиций:

значение >> количество

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

 int a = 32; a = a >> 2 // стало равным 8 

Крайние биты при сдвиге просто теряются. Например, значение 35 при сдвиге вправо на две позиции также приводит к значению 8, так как теряются два младщих бита.

00100011 35 >>2 ---------- 00001000 8

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

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

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

Иногда при выполнении сдвига вправо появление дополнительных знаковых разрядов нежелательно. В этом случае используется маскировка за счёт объединения значения со значением 0x0f оператором AND, что приводит к отбрасыванию любых битов дополнительных знаковых разрядов.

Сдвиг вправо без учёта знака

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

Допустим, мы хотим сдвинуть вправо на 24 бит значение -1 (в двоичном представлении 11111111 11111111 11111111 11111111):

11111111 11111111 11111111 11111111 >>> 24 --------------------------------------- 00000000 00000000 00000000 11111111 255 в двоичном виде типа int

Оператор >>> не столь полезен, поскольку имеет смысл только для 32- и 64-разрядных значений.

Побитовые составные операторы с присваиванием

Двоичные побитовые операторы имеют составную форму, которая объединяет побитовый оператор с оператором присваивания.

 a = a >> 4; a >>= 4; a = a | b; a |= b; 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *