Хакването на битове е това, което правите, когато четете или пишете отделни битове с по-голям брой. Четенето или писането на байтове е доста тривиално, но байтът е най-малката част, за която повечето езици биха предоставили функции. Ако искате да получите достъп до битовете, ще трябва да използвате така наречените побитови оператори като or, and, xor not или shift. Тъй като си играем с числа, операторът, за да получим това, което искаме, не е толкова ясен, колкото името на функцията. И се усеща ниско ниво, оттук и терминът „битово хакване“.
Има много причини, поради които бихте искали да направите това, но общата идея е, че искате да четете или записвате двоична информация, която не е ASCII или нещо друго, което вече няма библиотека. Ще видим примери по-късно в този урок. Моля, имайте предвид, че за простота всички числа в примерите се считат за uint8 (цели числа без знак, заемащи 8 бита).
Побитовите оператори
Предполагам, че е добре да се изясни разликата между „логическите“ оператори и тяхната „побитова“ противоположна част, защото при програмирането на високо ниво сме по-изложени на първото. Например често имаме израз if и 2 условия трябва да бъдат true.
if itIsTime and foodIsWarm:
eat()Как се дефинира „истинността“ във всеки програмен език не е непременно последователно и е източник на дебат, но по отношение на числата общото правило е „0“ е false, а всяко друго число е true. Докато побитовите оператори биха направили същото, но за всеки бит от числото.
Първо ще видим какво правят. Нека започнем с not, тъй като има само един операнд. Обикновено се представя със символа ~ тилда и основно инвертира всички битове на операнда.
~ 01010101
--------
= 10101010Ако бяхме използвали „логическо“ not вместо това, резултатът щеше да бъде false или 00000000, тъй като различно от нула е true.
Сега побитово and обикновено се представя с едно &. Всеки бит в резултата ще бъде '1', ако същият бит във всеки операнд също е '1'.
01010101
& 11000011
--------
= 01000001Побитово or обикновено се представя с едно |. Всеки бит в резултата ще бъде '1', ако поне един от двата операнда има същия бит, зададен на '1'.
01010101
| 11000011
--------
= 11010111Побитово xor обикновено се представя с ^. Подобно е на or с изключение на това, че всеки бит в резултата ще бъде '1', ако някой от операндите има същия бит, но не и двата. Оттук и името „изключително или“.
01010101
| 11000011
--------
= 10010110Последните 2 оператора са shift оператори, имате shift отляво и shift отдясно. Той основно премества битовете наляво или надясно. Има изключения, особено при числа със знак, но най-общо казано, когато битовете се преместят извън дължината на числото, се губят и въведените битове се настройват на '0'. Въпреки това има начин да се направи "кръгово" изместване, при което битове, които са изместени навън в една посока, се връщат обратно от другата страна. Ще видим това по-късно в урока.
Операторите за смени са представени с << и >>. Вторият операнд представлява броя на смените.
Shift 1 time to the left00111100 << 00000001 -------- = 01111000Shift 2 times to the right00111100 >> 00000010 -------- = 00001111
Сега, когато това е ясно. Нека видим някои примери от реалния живот.
Задайте и комбинирайте знамена
Един често срещан случай на използване на побитов оператор е, когато искате да зададете флагове. Това е, когато искате да използвате всеки бит от число, за да съхраните набор от булеви стойности (да или не, включено или изключено, вярно или невярно). Например в един байт можем да съхраним 8 булеви стойности.
Нека вземем много прост пример от реалния живот. Разрешенията на файл на компютър обикновено са представени от число с 3 флага за вашия личен достъп до него: правото да четете, пишете и изпълнявате файла (в този конкретен ред). Например, ако имате право да четете и изпълнявате файл, но не и право да пишете в него, флаговете като двоично число ще бъдат 101, защото само първият и третият флаг са включени. В повечето езици за програмиране това се изписва 0b101, което е 5 в десетичен знак (0b показва двоично число). Ако ви е позволено само да го четете, ще бъде 0b100.
Типичният начин за използване на това е всяка опция да бъде представена от число, което е само с включен единичен бит и да зададете опции с помощта на or. Ето пример за псевдокод:
READ = 0b100 # 4
WRITE = 0b010 # 2
EXECUTE = 0b001 # 1
setFilePermissions(
"/path/to/file.txt",
READ | EXECUTE
)Доста обичайно е да се задават двоични опции по този начин, особено в езици с ниско ниво като C. Можех да напиша числото 5 или 0b101 вместо READ | EXECUTE, но целта тук е да дам име на опциите веднъж завинаги и след това да използвам този слой абстракция, за да направи кода четлив.
Всяко число има само едно „1“ и представлява само един флаг. Следователно, когато използвате побитовия оператор or, вие основно комбинирате флаговете. Но в голямата схема на нещата принципът е, че ако искате да „включите“ конкретен бит в число, просто го or с число, което има само този бит. Например, ако искате да сте сигурни, че третият бит от числото е включен, вие го or с 0b100.
Като странична бележка казах, че сме направили кода по-„четлив“. Вярно е, но има нещо подвеждащо и тук терминът „хакване“ достига пълния си потенциал. Въпреки че е по-четлив от „5“, той все още изглежда като „ЧЕТЕТЕ или ИЗПЪЛНЯВАЙТЕ“, където всъщност задавате и двете, и е изкушаващо да използвате and вместо това. Повярвайте ми, ще свикнете с него, но един от начините да го видите е като списък с неща, които мога да правя: „Мога да чета или изпълнявам“.
В булевата алгебра or често се представя със знак +, а and се представя със знак за умножение ., което донякъде помага, но това е главно защото правилата за редуциране на уравнение съответно са доста сходни.
Маскиране на битове
Както можете да видите на страницата на Wikipedia за битово маскиране, повечето побитови оператори могат да се разглеждат като някакъв вид маскиране, но мисля, че е по-очевидно с оператора and. Обикновено го използваме, за да филтрираме конкретен бит или част от битове с това, което се нарича маска. И тогава можете да проверите дали стойността не е нула. Ако е, това означава, че битът е включен. Нека използваме отново нашия пример за разрешения за файлове. Имам разрешението като число и искам да тествам дали имам разрешение да го прочета.
READ = 0b100 # 4
WRITE = 0b010 # 2
EXECUTE = 0b001 # 1
filePermission = getPermission("/path/to/file.txt")
if (filePermission & READ) != 0:
print "yes"
else:
print "no"Ето какво се случва, ако разрешението за файл е 0b101:
101
& 100
---
= 100Можете да видите, че третият бит, започващ отдясно, е единственият бит в двете числа. Тъй като е в първото and второто число, този бит е зададен в резултата. И като следствие не е "0".
И ето какво се случва, ако разрешението за файл е 0b011:
011
& 100
---
= 000Тук операндът няма общ бит, следователно резултатът има „0“ навсякъде.
Сега можете да видите как второто число действа като маска. Всеки бит, който е "0" в маската, ще бъде "0" в резултата. Обичам да мисля за тях като за „изхвърлени“. Битовете, които са зададени на "1" на маската, се запазват точно както са на първото число. Обичам да мисля за тях като за „запазени“.
Да кажем, че исках да запазя само 4-те по-ниски бита от байта, можех да го and с маската 0b00001111.
10100011
& 00001111
--------
= 00000011виждаш ли Той „изхвърля“ от оригиналното число всички битове, които са „0“ в маската.
Компактни данни
Да приемем, че искаме да запазим числа във файл и искаме този файл да бъде възможно най-компактен. Знаем, че тези числа могат да бъдат само между 0 и 15. Можете да представите число между 0 и 15 само с 4 бита. Следователно, ако искаме да го направим компактен, можем да запазим 2 числа в 1 байт.
Начин да постигнете това е да shift едно от числата 4 пъти вляво и след това да използвате or, за да ги комбинирате. Тъй като и двете числа са под или равни на 15, ние знаем, че всеки бит над 4-ия бит е задължително неуместен и е зададен на нула. Следователно изместването на едно от числата с 4 бита наляво ни позволява да комбинираме 2-те числа, без да имаме припокриване. Всички значими битове на всяко число са в неговата собствена половина.
number1 = 0b00001010 # 10
number2 = 0b00001100 # 12
shifted1 = number1 << 4 # 0b10100000
combined = shifted1 | number2 # 0b10101100След това можете да запишете тези числа във файл и той ще заеме половината място. За да ги прочетете от файла. Можете да използвате and, за да маскирате съответната част и да изместите първата в обратната посока.
combined = 0b10101100
number1 = (combined & 0b11110000) >> 4 # 0b00001010
number2 = combined & 0b00001111 # 0b00001100Този процес всъщност е начинът, по който бихте отпечатали байтове в шестнадесетичен (напр. „A0“), защото всеки знак е точно между 0 и 15. Той е разделен на 2 знака. Следователно първо трябва да извлечете двете шестнадесетични числа и след това да отпечатате знаците им между „0“ и „F“.
Кръгова смяна
Както бе споменато по-рано, има начин да се направи shift „кръгов“, тоест shift, където битовете, които преливат от едната страна, се връщат обратно от другата страна. Ето как бихте направили ляво shift от 3:
number = 0b11110000
circLeftShifted =
(number << 3) | (number >> (8 - 3)) # 0b10000111Трябва да е доста разбираемо. Първо правим нормално ляво shift и го комбинираме с помощта на or със същото число, което е изместено в другата посока от допълнителния брой места.
XOR Космическият шериф
Сигурен съм, че ще забележите, че запазих xor за края. Честно казано, трудно ми беше да намеря добър случай за използване на xor, който не е нито твърде прост, нито твърде сложен. Но всъщност има основателна причина за това: xor всъщност е магьосникът на всички тях. Искам да кажа, че всички битови оператори са магически по свой начин, но xor е най-интригуващият. Вероятно затова X-OR, един от най-великите космически шерифи на всички времена, е кръстен на него (във френската версия). Ето защо вместо подробни примери, ще се концентрираме върху интересните му свойства.
В простия край на спектъра ще откриете, че можем да използваме xor по същия начин, по който използваме or в нашия пример за разрешения за файлове, с изключение на това, че вместо да зададе бита на '1', той го превключва. Това вече е много интересен имот. In всъщност прави същото като оператора not, с изключение на това, че можете да контролирате кои битове да се обърнат. Маскирате с '1' битовете, които искате да обърнете/превключите.
Друга особеност на xor е, че ако xor число със себе си, то връща всички '0'. Ето защо се използва в контролни суми за сравняване на числа. Използва се и с графики, хеширане, компресия, криптография. В много случаи един особено интересен аспект на xor, който се използва, е фактът, че вероятността за разпределение на неговия изход е 50%, което не е случаят с or и and.
Нека проверим „таблицата на истината“ или тези оператори, за да визуализираме това:
a | b | a AND b --------------- 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1a | b | a OR b -------------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 1a | b | a XOR b --------------- 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0
Както можете да видите, изходът на and има повече шансове да бъде '0', а изходът на or има повече шансове да бъде '1'. Само изходът на xor е балансиран. Това го прави интересен за „хеш функциите“. Можете да комбинирате числа и поради балансирания изход намалявате шансовете за сблъсък на два клавиша.
Знам, че всичко това е малко абстрактно, но в най-простата му форма, ако искате да хеширате списък с числа (или нещо друго, тъй като всичко е число в компютъра) в едно число за бързо сравнение, можете да ги xor всички .
hashForPin = 4 ^ 2 ^ 9 ^ 6
hashForDad = 'd' ^ 'a' ^ 'd'Моля, имайте предвид, че има голям проблем с това, така че не го използвайте в кода си, освен ако не знаете последствията. Върши добра работа при избягване на сблъсъци (изходът е същият за други числа или думи), но не взема под внимание реда. Тоест, ако хеширате думата „татко“ и думата „добавяне“, резултатът ще бъде еднакъв и за двете. Ето защо има тонове алгоритми за хеширане, които са много по-сложни от просто xoring на числата. Но това е градивният елемент за тях.
Очевидно фактът, че редът няма значение, също може да бъде използван. Може да е точно това, което искате.
Заключение
Части в кода, където използвате побитови оператори, обикновено са трудни за четене, затова ви насърчавам да ги скриете под конкретна функция с ясно име. За да дадем повече примери, ще публикуваме друга статия, коментираща проект, използващ някои от тези принципи.
