Kaip veikia lyginio ar nelyginio skaičiaus ir bitų analizatorius

Šis įrankis nustato bet kurio sveikojo skaičiaus lyginumą (paritetą) ir dvejetainę struktūrą tiesiogiai jūsų naršyklėje, naudodamas integruotą neriboto tikslumo BigInt aritmetiką. Skirtingai nuo standartinių skaičiuotuvų, kuriuos riboja IEEE-754 dvigubo tikslumo slankiojo kablelio lubos (Number.MAX_SAFE_INTEGER = 253 − 1 = 9 007 199 254 740 991) ir kuriuose išraiška 9007199254740993 % 2 dėl mantisos apvalinimo klaidingai grąžina lyginį rezultatą, BigInt variklis išlaiko absoliutų kiekvieno bito tikslumą skaičiams, turintiems šimtus ar tūkstančius skaitmenų. Galite įvesti įprastą dešimtainį skaičių, neigiamą sveikąjį skaičių, šešioliktainę reikšmę su priešdėliu 0x arba dvejetainį kodą su 0b — visi diagnostiniai skydeliai atsinaujina akimirksniu be jokių užklausų į serverį.

Analizatorius išskaido kiekvieną skaičių į keturis inžinerinius pjūvius:

  • Momentinis verdiktas ir LSB bitų juosta: Parodo, ar skaičius n yra LYGINIS (n = 2k), ar NELYGINIS (n = 2k + 1), ir vizualizuoja paskutinius 8 bitus (nuo 7 bito iki 0 bito), išskirdamas mažiausiai reikšmingą bitą (LSB), kuris tiesiogiai lemia lyginumą.
  • Bitų ir skaičiavimo sistemų inspektorius: Atvaizduoja žemutinius 32 bitus papildomojo kodo (two's complement) dvejetaine forma su paryškintu LSB bitu, tikslią šešioliktainę (Base 16) ir aštuntainę (Base 8) išraišką, Hamingo svorį (įjungtų 1 bitų skaičių — popcount) su aparatiniu pariteto bitu bei galinių nulių skaičių (ctz), nurodantį didžiausią dvejeto laipsnį (2r), iš kurio dalijasi n.
  • Matematinės savybės ir dalumo matrica: Tikrina, ar skaičius yra pirminis (daliklių paieška ir deterministinis 12 bazių Milerio-Rabino testas), ar jis yra dešimtainis palindromas, tobulasis kvadratas (√n), Fibonačio sekos narys (pagal Geselio kriterijų 5n2 ± 4), ir apskaičiuoja tikslias liekanas dalijant iš 2, 3, 4, 5, 6, 8, 9, 10, 12.
  • Masinis skaičių sąrašo skirstytuvas (Batch Mode): Įklijavus bet kokį skaičių sąrašą, akimirksniu išskirsto juos į lyginių ir nelyginių stulpelius bei suskaičiuoja tikslius kiekius, procentines dalis, bendrą BigInt sumą (Σ) ir aritmetinį vidurkį (μ).

Dvejetainė LSB (n & 1) kaukė ir procesoriaus ALU logika

Dvejetainėje pozicinėje skaičiavimo sistemoje bet kuris neneigiamas sveikasis skaičius n užrašomas kaip dvejeto laipsnių daugianaris: n = bm2m + bm−12m−1 + … + b121 + b020, kur kiekvienas bitas bi ∈ {0, 1}. Kiekvienas narys nuo b121 ir aukščiau turi daugiklį 2, todėl be liekanos dalijasi iš 2. Dėl šios priežasties visa skaičiaus n dalybos iš 2 liekana priklauso išimtinai nuo paskutiniojo nario b0 × 20 = b0, vadinamo mažiausiai reikšmingu bitu (Least Significant Bit — LSB).

Procesoriaus aritmetiniame-loginiame įrenginyje (ALU) lyginumo patikrai niekada nenaudojama dalybos grandinė. Sveikųjų skaičių dalyba (x86-64 instrukcijos DIV / IDIV) reikalauja keliolikos taktų ciklo, tuo tarpu bitinė „IR“ (AND) kaukė su vienetu — (n & 1) === 0 arba asemblerio instrukcija TEST RAX, 1 — įvykdoma per vieną procesoriaus taktą (~0,25 nanosekundės), tiesiogiai nuskaitant žemiausią registro laidą. Kadangi šiuolaikinės architektūros neigiamus sveikuosius skaičius saugo papildomuoju kodu (two's complement) — invertuojant visus bitus ir pridedant 1 — LSB taisyklė identiškai galioja ir neigiamiems skaičiams: −42 baigiasi bitais …110101102 (LSB = 0, lyginis), o −1337 baigiasi …110001112 (LSB = 1, nelyginis). Be to, suskaičiavus galinius nulius iki pirmojo 1 bito (aparatine instrukcija TZCNT / BSF), iškart gaunamas tikslus 2-adinis rodiklis ν2(n): jei skaičius dvejetainėje sistemoje baigiasi trimis nuliais (…10002), jis garantuotai dalijasi iš 23 = 8.

Matematinis nulio (0) lyginumo įrodymas ir GF(2) žiedo algebra

Vienas dažniausių klausimų tiek mokykliniuose egzaminuose, tiek programavimo interviu yra tai, ar nulis (0) yra lyginis, nelyginis, ar „nei toks, nei toks“. Pagal griežtą skaičių teorijos apibrėžimą sveikasis skaičius n ∈ ℤ yra lyginis tada ir tik tada, kai egzistuoja toks sveikasis skaičius k ∈ ℤ, kad n = 2k. Įstačius k = 0 (kuris yra pilnateisis sveikųjų skaičių aibės ℤ elementas), gauname:

0 = 2 × 0 ⇒ 0 mod 2 = 0

Nulis be jokių išimčių tenkina visas lyginių skaičių algebrines savybes: skaičių tiesėje jis stovi tarp dviejų nelyginių skaičių (−1 ir +1); pridėjus nulį prie bet kurio lyginio skaičiaus gaunamas lyginis skaičius (2a + 0 = 2a); o visi jo dvejetainės išraiškos bitai yra nuliai (0 & 1 = 0). Abstrakčiojoje algebroje sveikųjų skaičių aibės suskaidymas į lyginių ([0]) ir nelyginių ([1]) ekvivalentumo klases sudaro faktorinį žiedą ℤ/2ℤ, dar vadinamą Galua kūnu GF(2). Šiame kūne pariteto sudėtis ir atimtis tiesiogiai atitinka loginį XOR ventilį (^): Lyginis ± Lyginis = Lyginis (0 ^ 0 = 0), Nelyginis ± Nelyginis = Lyginis (1 ^ 1 = 0) ir Lyginis ± Nelyginis = Nelyginis (0 ^ 1 = 1). Tuo tarpu pariteto daugyba atitinka loginį AND ventilį (&): padauginus iš lyginio skaičiaus visada įvedamas daugiklis 2 (0 & x = 0), todėl sandauga yra nelyginė tik tada, kai visi dauginamieji yra nelyginiai (1 & 1 = 1).

Telekomunikacijų pariteto bitai ir „is-even“ NPM paketų ironija

Bitų inspektoriuje matote dvi skirtingas, bet glaudžiai susijusias sąvokas: skaičiaus lyginumą (ar sveikojo skaičiaus reikšmė n dalijasi iš 2, ką nusako vien tik 0-inis bitas) ir bitų paritetą / Hamingo svorį (ar visų įjungtų 1 bitų suma dvejetainiame žodyje, skaičiuojama procesoriaus POPCNT instrukcija, yra lyginė ar nelyginė). Nuosekliosiose telekomunikacijų sąsajose (RS-232 UART kadruose), PCI magistralėse, RAID-5 diskų masyvuose ir ECC serverių atmintyje prie kiekvieno duomenų paketo pridedamas papildomas pariteto bitas, kad bendras Hamingo svoris išliktų pastoviai lyginis (Even Parity) arba nelyginis (Odd Parity). Jei dėl elektromagnetinių trikdžių ar kosminės spinduliuotės perdavimo metu apsiverčia vienas bitas, imtuvo XOR grandinė aparatiniame lygmenyje akimirksniu užfiksuoja pariteto nesutapimą ir atmeta sugadintą kadrą.

Kitame programų inžinerijos poliuje egzistuoja garsusis JavaScript ekosistemos kuriozas — is-odd ir is-even NPM paketai. Nors lyginumo patikra yra keturių simbolių procesoriaus operacija (n & 1), šie mikro-paketai kasmet surenka šimtus milijonų atsisiuntimų, kur paketas is-even tiesiog importuoja priklausomybę is-odd ir invertuoja jos loginę reikšmę (!isOdd(n)), o satyriniai projektai generuoja tūkstančius if (n === 1) return false; eilučių arba kreipiasi į dirbtinio intelekto API vienam bitui patikrinti. Kai jūsų sistemai reikia klasifikuoti didelius sveikuosius skaičius, tirti bitų kaukes ar išskirstyti duomenų masyvą, vietinė BigInt ir bitinių operatorių logika atlieka milijonus patikrų per sekundę be jokių išorinių bibliotekų.