Част 4: Побитови модели

Побитова измамна таблица за операции (¬, ‹‹, ››, ROTR/L, +, ∧, ∨, ⊕)

Ние обяснихме в Част 1 какво представляват битовите низове, а в Част 2 и 3, че интересни модели могат да бъдат намерени в побитови операции като И и ИЛИ. В част 4 ние ускоряваме тези открития, като представяме ключови побитови операции и техните модели с минимални коментари. Обичайни предупреждения: използвам обозначенията, намерени в FIPS 180–4; приемете, че битовите низове са представяния само на положителни цели числа, най-значимият бит вляво.

В следващите примери работим с битови думи с фиксирана дължина n и отбелязваме a, b две n-битови думи. За примерите и илюстрациите задаваме n=6, така че 6-битовите думи a, bпредставляват положителни цели числа между 0 и 63.

Побитови операции върху една битова дума

Отрицание (¬): допълнение на единици

Отрицанието на a,отбелязано¬a,е битов низ, съдържащ нули, където a съдържа единици и единици, където a съдържа нули.
Сумата от aи нейното отрицание ¬a е битов низ, съдържащ само единици, така че можем да напишем:a + ¬a = 2ⁿ,или еквивалентно, ¬a = 2ⁿ− a

      a = 011010 (26)
     ¬a = 100101 (37)
          --------
 a + ¬a = 111111 (63)

Преместване наляво (‹‹ k): умножение по 2ᵏ

a≪k,е n-битов низ, където всички битове на aса изместени наляво с kслота, с вмъкнати нули отдясно
В резултат на това a≪k = a⋅ 2ᵏ mod 2ⁿ. Модулът показва, че n-битов низ не може да съдържа числа, по-големи от 2ⁿ.
Единичните леви смени са удобен начин за умножение по 2 на „ниска“ цена, като се приеме, че няма преливане: a≪1 = 2⋅ a mod 2ⁿ

     a = 011010 (26)
a << 1 = 110100 (52) # i.e., 26 ⋅ 2
a << 2 = 101000 (40) # i.e. 52 ⋅ 2 - 64 (overflow)

Преместване надясно (›› k): деление на 2ᵏ

a≫k,е n-битов низ, където всички съществуващи битове на aса изместени надясно с kслота, с вмъкнати нули отляво
Забележка: в езици като JavaScript, ≫ е малко по-различна операция добавяне на единици отляво; дясно изместване, както е описано тук, се отбелязва ⋙ вместо това (и всъщност ›› и ››› съответно — просто не харесвам форматирането на Medium за тях)
a≫k = под (a / 2ᵏ)

     a = 011010 (26)
a >> 1 = 001101 (13) # 26 / 2
a >> 2 = 000110 (6) # 13 / 2 - 0.5

Завъртане наляво (ROTL): ляво преместване с усукване

ROTL(a, k) е кръгово изместване вляво на битов низ aпо k слота. Тоест ROTL е ляво изместване, където препълващите битове отляво се добавят обратно вдясно, вместо нули.
В резултат на това за всяка стойност на kмежду 0 и n-1,ROTL може да се запише като:

         a = 011010 (26)
ROTL(a, 1) = 110100 (52) # i.e., 26⋅2
ROTL(a, 2) = 101001 (41)# i.e., 26⋅4 mod64 + 1

Завъртане надясно (ROTR): завъртане наляво

ROTR(a, k) е кръгово изместване надясно на битов низ aпо k слота. Тоест ROTR е дясно изместване, където препълващите се битове вдясно се добавят обратно вляво, вместо нули.
Като алтернатива можете да проверите, че като цяло ROTR(a, k) = ROTL(a, n−k),така че ROTR е напълно дефиниран от ROTL.

Побитови операции върху две битови думи

Модул за добавяне 2ⁿ (+)

(a + b) е n-битова дума, съответстваща на числовата сума на a и b, модул 2ⁿ. Модулът показва, че n-битова дума не може да съхранява стойности, по-големи от 2ⁿ.

    a = 011010 (26)
    b = 101001 (41)
        --------
a + b = 000011 (3) # i.e., 26 + 41 - 64 (overflow!)

И (∧)

(a∧b) е n-битова дума с единицисамо където и двете a и b имат единици
И графиката е организирана в блокове с размер 2ᵏ, съставени от четири квадранта: 3 еднакви блока tₖотляво и отдолу и един доминиращ блок Tₖ в горния десен ъгъл, така че Tₖ = tₖ + 2ᵏ
Блокове с размер 2ᵏсъставляват най-левия квадрант (tₖ₊₁) на следващия по-голям блок с размер 2ᵏ⁺¹
Вижте Част 2: Красотата на побитовото И за подробно обсъждане на свойствата и модела на функцията и обяснение на това, което означавам под обозначенията Tₙ, tₙ и т.н..

Опасност! Моя собствена интерпретация в „блокове“, „квадранти“, „нива“: използвайте с повишено внимание.

Част 2: Красотата на побитово И (∧ или &)
Изследване и визуализиране на многото аспекти на побитовата И операцияmedium.com

    a = 011010 (26)
    b = 101001 (41)
        --------
a ∧ b = 001000 (8)

OR (∨)

(a∨b) е n-битова дума с единици, където или a или b имат единици
Подобно на И, ИЛИ е организирано в блокове с размер 2ᵏ, съставени от четири квадранта. Този път само един блок с ниска стойност, разположен в долния ляв ъгъл на блока и отбелязан tₖ,и 3 идентични блока с висока стойност Tₖвдясно и отгоре, така че Tₖ = tₖ + 2ᵏ.
Блокове с размер 2ᵏсъставляват най-левия квадрант (tₖ₊₁) на следващия по-голям блок с размер 2ᵏ⁺¹
Въпреки приликите, ИЛИ се различава от И: инициализиращите блокове T1 и подредбата на квадрантите в блоковете са различни; и блоковете са ограничени от различни „критични“ стойности (степени на 2 за И и техните предшественици за ИЛИ). За повече информация относно нюансите на ИЛИ срещу И, вижте Част 3: Побитово ИЛИ, брат на И

Отново, опасност: мое тълкуване в „блокове“, „квадранти“, „нива“. Използвайте с повишено внимание.

Част 3: Побитово ИЛИ, брат на И
Преглед на побитовата ИЛИ функция (∨ или |) и нейната връзка с И.medium.com

    a = 011010 (26)
    b = 101001 (41)
        --------
a + b = 111011 (59)

Разглеждайки моделите, изглежда ясно, че И и ИЛИ трябва да са свързани чрез някаква връзка. Всъщност си струва да се споменат поне две:

(a∧b) + (a∨b) = a+b. Наложените графики И и ИЛИ правят графиката на добавяне. Като алтернатива, (a∨b) = (a+b) − (a ∧ b): a или b, е всичко в a плюс всичко в b, минус двойно преброената част в пресечната точка на a и b.
(a∨b) =¬(¬a∧¬b). ИЛИ графиката е точно И графиката, с обърната цветова схема и обърнати оси. В алтернативен запис, (a∨b) +(¬a∧¬b)= 2ⁿ .

XOR (⊕)

    a = 011010 (26)
    b = 101001 (41)
        --------
a ⊕ b = 110011 (51)

(a⊕b) е n-битова дума с единици, където или a или b имат едно но не и двете.
Досега вече очаквате, че XOR също е организиран в блокове с размер 2ᵏ; всеки от четири квадранта; 2 квадранта с ниска стойност, отбелязани tₖ,долу вляво и горе вдясно; 2 такива с висока стойност, отбелязани Tₖ, горе вляво и долу вдясно; Tₖ = tₖ + 2ᵏ. И блоковете с размер 2ᵏ правят най-левия квадрант (tₖ₊₁) на следващия по-голям блок с размер 2ᵏ⁺¹.

(a⊕b) + (a∧b) = (a∨b). XOR има точно достатъчно светлина в своите квадранти с висока стойност (долу вдясно, горе вляво), за да превърне тъмния модел И в ярък модел ИЛИ. Алтернативно, (a⊕b) = (a∨b) − (a∧b): a XOR b е всичко, което е в a или в b, минус всичко, което е и в a, и в b.

Побитово добавяне

Наблюдателните сигурно са забелязали, че добавянето е единствената операция тук, която дефинирах само числено, без да обяснявам какво е направила на битова основа. Всъщност добавянето е единствената операция на тази страница, която не се квалифицира като побитова операция според Wikipedia, тъй като тя не „работи с един или повече битови модели или двоични числа в ниво на отделните им битове”.

Възможно е обаче добавянето да се дефинира като побитова операция, т.е. като операция, дефинирана преди всичко от това, което прави с битовете на два n-битови низа. Да го направим.

Отбелязваме a, bдвата n-битови низа и sтяхната сума по модул 2ⁿ: s = a + b; и отбелязваме aᵢ, bᵢ, sᵢ,i-тите битове в тези битови низове, така че например a може да се запише като: aₙ₋₁aₙ₋₂…a₂a₁a₀.

Задаваме s₀ = a₀ ⊕ b₀ и отбелязваме c пренасянето на тази операция: c = a₀ ∧ b₀
За всяко 0 ‹ i ‹ n-1,дефинираме: sᵢ = (aᵢ ⊕ bᵢ)⊕ c и предефинираме пренасянето cтака че c =((aₖ⊕ bₖ)∧c) ∨(aₖ∧ bₖ)
И накрая, за i = n-1,просто задаваме s = aₙ₋₁ ⊕ bₙ₋₁⊕ c

Този метод е много подобен на алгоритъма за добавяне, който всички сме учили в началното училище. Първа стъпка, изчислете сумата от най-десните цифри. Ако сумата им е повече от 1 (т.е. a₀ ∧ b₀ = 1), носете 1 и бутнете нула (a₀ ⊕ b₀ = 0). Ако не, не носете (a₀ ∧ b₀ = 0),а хвърлете едно, ако някой от битовете е едно, или нула, ако и двата бита са нули (a₀ ⊕ b₀). Повторете стъпките за всички числа отляво, но като вземете предвид този път пренасянето, ако има такова, и т.н. и т.н.

И... Направихме го! Сега имаме побитова дефиниция на добавянето. Истинският въпрос обаче е дали имаме нужда от такъв и ако да, защо? Е, доколкото разбираме какво прави добавката, вероятно нямаме нужда от такава. Въпреки това, тези инструкции всъщност ни позволяват да създадем основен „електронен суматор“, използвайки само „логически порти“. На свой ред тези суматори и логически портове помагат за създаването на „аритметични логически единици“, които са градивни елементи в CPU, GPU, FPU. И така – кой знае – чрез изследване на прости побитови операции, ние хвърлихме първия си поглед към света на изчисленията, използващи електронни схеми.

Има още няколко операции, които можем да отделим време за дефиниране тук, но сме дефинирали достатъчно концепции, за да можете да ги изследвате по-задълбочено, ако желаете; и което е по-важно, дефинирахме всички операции, от които се нуждаем, за да обсъждаме важни предстоящи теми: хеширане и шифроване.

Благодаря, че стигнахте дотук и ако забележите грешки, моля, уведомете ме в коментар. Приятен ден!