Bitvise operatorer: AND, OR, XOR, NOT og skift

Bitmanipulation lader dig arbejde direkte med heltals binære repræsentation. Mange problemer, der virker komplekse, bliver trivielle med det rette bitvise trick: at finde et manglende tal på O(n)-tid og O(1)-plads, at bytte variable uden en midlertidig variabel eller at kode delmængder kompakt. Interviewere bruger disse opgaver til at afprøve forståelse på lavt niveau og kreativ tænkning.

Heltal i Python har vilkårlig præcision — de kan være så store, som hukommelsen tillader — men bitoperationer følger altid standardsemantik for to-komplement på hardwareniveau. Alle seks operatorer arbejder bit for bit på heltallenes binære repræsentationer.

AND-operatoren (&) giver kun 1, når begge inputbits er 1. Den bruges primært til maskering: at udvælge bestemte bits i et tal og samtidig nulstille alle andre. For at kontrollere, om bit k er sat i tallet n, skal du evaluere n & (1 << k) — hvis resultatet ikke er nul, er bit k lig med 1.

AND bruges også til at nulstille den laveste satte bit: n & (n - 1) fjerner bitten længst til højre med værdien 1. Det bruges til effektiv optælling af satte bits og til at kontrollere, om et tal er en potens af to (en potens af to har præcis én sat bit, så n & (n-1) == 0).

OR-operatoren (|) giver 1, hvis mindst én inputbit er 1. Den bruges primært til at sætte en bestemt bit til 1 uden at påvirke de andre. For at sætte bit k i tallet n skal du bruge n | (1 << k). Den 1'er, der forskydes til position k, tænder den pågældende bit; alle andre bits forbliver uændrede, fordi OR med 0 bevarer værdien.

OR bruges også til at kombinere flag: Hvis du repræsenterer funktionsflag som individuelle bits, kan du aktivere flere flag med OR. Eksempelvis kombinerer READ | WRITE | EXECUTE tre tilladelsesbits til ét heltal.

XOR-operatoren (^) giver 1, når inputbittene er forskellige. XOR har tre stærke algebraiske egenskaber: a ^ a = 0 (ens input ophæver hinanden), a ^ 0 = a (nul er identitetselementet), og XOR er både kommutativ og associativ. Disse egenskaber gør XOR til det oplagte værktøj til at finde entydige elementer.

XOR bruges også til at skifte en bestemt bit: n ^ (1 << k) vender bit k, mens de andre forbliver uændrede. Hvis bit k var 0, bliver den 1; hvis den var 1, bliver den 0.

NOT-operatoren (~) inverterer alle bits. I Python er ~n lig med -(n+1) på grund af to-komplementrepræsentationen. Det overrasker mange: ~5 = -6, ikke den naivt forventede 0b11111010. Heltal i Python har uendelig præcision, så hvis du vender alle bits i et positivt tal, får du et negativt resultat i to-komplement.

I praksis bruger du sjældent ~ alene i Python til bitmanipulation. Brug det i stedet sammen med AND til at nulstille bestemte bits, eller beregn ~n & mask, hvor mask begrænser bredden til et bestemt antal bits (f.eks. & 0xFFFFFFFF for 32-bit).

Venstreforskydningsoperatoren (<<) forskyder alle bits mod venstre med k positioner og udfylder de ledige positioner til højre med nuller. Det svarer til at multiplicere med 2^k. En venstreforskydning med 1 fordobler værdien; en venstreforskydning med k multiplicerer med 2^k.

I interviewopgaver bruges venstreforskydninger oftest til at oprette bitmasker: 1 << k opretter et tal, hvor kun bit k er sat. Det er grundlaget for alle bitmanipulationsoperationer — at sætte, nulstille, skifte og kontrollere individuelle bits begynder med 1 << k.

Højreforskydningsoperatoren (>>) forskyder alle bits mod højre med k positioner og kasserer de k bits længst til højre. Det svarer til heltalsdivision med 2^k. Højreforskydning i Python er altid aritmetisk: de bits, der kommer ind længst til venstre, udfyldes med fortegnsbitten (0 for positive tal, 1 for negative).

Et almindeligt interviewtrick er at udtrække bit k fra tallet n med (n >> k) & 1. Det forskyder bit k ned til position 0 og maskerer alle andre bits væk. Det er den enkleste måde at kontrollere en bestemt bit på uden at skulle beregne og sammenligne en komplet maske.

Her er en samling af de mest almindelige idiomer inden for bitmanipulation, som du vil møde i interviews. Lær disse mønstre udenad — de går igen i dusinvis af opgaver:

• n & 1 — kontrollér, om n er ulige
• n & (n-1) — nulstil den laveste satte bit
• n & -n — isolér den laveste satte bit
• n | (1 << k) — sæt bit k
• n & ~(1 << k) — nulstil bit k
• n ^ (1 << k) — skift bit k
• (n >> k) & 1 — kontrollér bit k

At tælle antallet af bits med værdien 1 i et heltal kaldes bitoptælling (popcount). Den naive tilgang gennemløber alle bits. Brian Kernighan-tricket er hurtigere: nulstil gentagne gange den laveste satte bit med n &= n - 1, og tæl iterationerne, indtil n bliver 0. Hver iteration fjerner præcis én bit med værdien 1, så løkken kører nøjagtig lige så mange gange, som der er bits med værdien 1.

Python 3.10+ har int.bit_count(), som returnerer antallet direkte. I ældre versioner er Kernighan-tricket den almindelige manuelle tilgang. Denne teknik løser også problemet 'Hamming-vægt' på LeetCode.

I modsætning til C/Java er heltal i Python vilkårligt store — der findes ikke 32-bit- eller 64-bit-overløb. Derfor skal du selv maskere resultater til en fast bredde, når du løser opgaver, der forventer 32-bit-adfærd: brug & 0xFFFFFFFF for kun at beholde de nederste 32 bits.

NOT-operatoren ~n i Python returnerer -(n+1), ikke den bitinverterede version, som du måske forventer fra C. I 32-bit-opgaver skal du bruge ~n & 0xFFFFFFFF eller beregne 0xFFFFFFFF ^ n for at få det forventede 32-bit-komplement. Disse forskelle volder problemer for mange kandidater, der er vant til bitmanipulation i C-stil.

Venstre- og højreforskydninger er en ekstremt hurtig måde at multiplicere eller dividere med potenser af to på. På hardware er bitforskydninger operationer med én instruktion, mens multiplikation og division kræver flere cyklusser. I Python er heltalsmultiplikation allerede effektiv, men forståelsen af sammenhængen hjælper dig med at se bitmønstre tydeligere.

En nyttig identitet er: For at kontrollere, om n er et multiplum af 2^k, skal du bruge (n & (2^k - 1)) == 0. Masken 2^k - 1 har alle de nederste k bits sat til 1; en AND-operation med den giver resten ved division med 2^k. Det svarer til n % (2^k), men er hurtigere i C-baserede sprog.

I denne lektion lærte du, at: AND maskerer bits, OR sætter bits, XOR skifter bits og registrerer forskelle, NOT inverterer (giver -(n+1) i Python), og forskydninger multiplicerer/dividerer med potenser af to, n & (n-1) nulstiller den laveste satte bit og danner grundlag for kontrol af potenser af to og bitoptælling, og Python har ikke overløb med fast bredde, så 32-bit-opgaver kræver eksplicit maskering med & 0xFFFFFFFF. Næste lektion undersøger vi XOR's selv-inverse egenskab for at løse familien af problemer med ét enkelt tal.