Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar
Repetera alla sex bitvisa operatorer med sanningstabeller och Python-exempel och förstå hur vänster- och högerskiftning motsvarar multiplikation respektive division med två.
Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Varför bitmanipulering är viktigt
Bitmanipulering låter er arbeta direkt med heltalens binära representation. Många problem som verkar komplexa blir triviala med rätt bittrick: att hitta ett saknat tal på O(n)-tid och O(1)-utrymme, byta plats på variabler utan en temporär variabel eller koda delmängder kompakt. Intervjuare använder dessa problem för att testa förståelse på låg nivå och kreativt tänkande.
Python-heltal har godtycklig precision — de kan vara så stora som minnet tillåter — men bitoperationer följer alltid standardsemantiken för tvåkomplement på hårdvarunivå. Alla sex operatorer arbetar med heltalens binära representation bit för bit.
# All six bitwise operators in Python
a, b = 0b1010, 0b1100 # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b (AND) = {bin(a & b)} = {a & b}') # 1000 = 8
print(f'a | b (OR) = {bin(a | b)} = {a | b}') # 1110 = 14
print(f'a ^ b (XOR) = {bin(a ^ b)} = {a ^ b}') # 0110 = 6
print(f'~a (NOT) = {~a}') # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5AND-operatorn: bitmaskering
AND-operatorn (&) ger resultatet 1 endast när båda inmatningsbitarna är 1. Dess huvudsakliga användning är maskering: att välja ut specifika bitar i ett tal och samtidigt nollställa alla andra. För att kontrollera om bit k är satt i talet n beräknar ni n & (1 << k) — om resultatet inte är noll är bit k 1.
AND används också för att rensa den lägsta satta biten: n & (n - 1) tar bort den högra 1-biten. Detta används för att räkna satta bitar effektivt och för att kontrollera om ett tal är en tvåpotens (en tvåpotens har exakt en satt bit, så n & (n-1) == 0).
n = 0b10110100 # 180
# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}') # 1
# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}') # 10110000, removed the '100'
# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
is_pow2 = x > 0 and (x & (x - 1)) == 0
print(f'{x}: power of 2 = {is_pow2}')OR-operatorn: sätta bitar
OR-operatorn (|) ger resultatet 1 om minst en inmatningsbit är 1. Dess huvudsakliga användning är att sätta en specifik bit till 1 utan att påverka övriga bitar. För att sätta bit k i talet n använder ni n | (1 << k). Ettan som skiftas till position k aktiverar den biten; alla andra bitar förblir oförändrade eftersom OR med 0 ger samma värde.
OR används också för att kombinera flaggor: om ni representerar funktionsflaggor som enskilda bitar kan ni aktivera flera flaggor med OR. Exempelvis kombinerar READ | WRITE | EXECUTE tre behörighetsbitar till ett heltal.
# Set bit k in n
def set_bit(n, k):
return n | (1 << k)
n = 0b1000 # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}') # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}') # 1001
# Flag combination example
READ = 0b001 # 1
WRITE = 0b010 # 2
EXECUTE = 0b100 # 4
perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ: {bool(perms & READ)}')
print(f'Has WRITE: {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')XOR-operatorn: växling och skillnader
XOR-operatorn (^) ger resultatet 1 när inmatningsbitarna skiljer sig åt. XOR har tre kraftfulla algebraiska egenskaper: a ^ a = 0 (samma indata tar ut varandra), a ^ 0 = a (noll är identitetselementet), och XOR är både kommutativ och associativ. Dessa egenskaper gör XOR till det självklara verktyget för att hitta unika element.
XOR används också för att växla en specifik bit: n ^ (1 << k) inverterar bit k samtidigt som övriga bitar lämnas oförändrade. Om bit k var 0 blir den 1; om den var 1 blir den 0.
# XOR properties
print(5 ^ 5) # 0 — same values cancel
print(5 ^ 0) # 5 — zero is identity
print(5 ^ 3 ^ 3) # 5 — 3 cancels itself
# Toggle bit k
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}') # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # 1011 (was 0)
# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b # b now gets original a
a = a ^ b # a now gets original b
print(f'After XOR swap: a={a}, b={b}') # a=13, b=7NOT-operatorn och tvåkomplement
NOT-operatorn (~) inverterar alla bitar. I Python är ~n lika med -(n+1) på grund av tvåkomplementsrepresentationen. Detta överraskar många: ~5 = -6, inte det naivt förväntade 0b11111010. Python-heltal har oändlig precision, så att invertera alla bitar i ett positivt tal ger ett negativt resultat i tvåkomplement.
I praktiken använder ni sällan ~ ensamt i Python för bitmanipulering. Använd det i stället tillsammans med AND för att rensa specifika bitar, eller beräkna ~n & mask där mask begränsar bredden till ett visst antal bitar (till exempel & 0xFFFFFFFF för 32 bitar).
# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
print(f'~{n} = {~n}') # all give -(n+1)
# Clear bit k using NOT
def clear_bit(n, k):
return n & ~(1 << k)
n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}') # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}') # 1110
# Limiting to 32-bit with mask
def bitwise_not_32(n):
return ~n & 0xFFFFFFFF
print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}') # 32 zeros then onesVänsterskift: multiplicera med tvåpotenser
Vänsterskiftsoperatorn (<<) skiftar alla bitar åt vänster med k positioner och fyller de tomma positionerna till höger med nollor. Detta motsvarar multiplikation med 2^k. Ett vänsterskift med 1 fördubblar värdet; ett vänsterskift med k multiplicerar det med 2^k.
I intervjuproblem används vänsterskift oftast för att skapa bitmasker: 1 << k skapar ett tal där endast bit k är satt. Detta är grunden för alla bitmanipuleringsoperationer — att sätta, rensa, växla och kontrollera enskilda bitar börjar med 1 << k.
# Left shift = multiply by 2^k
n = 1
for k in range(8):
print(f'1 << {k} = {1 << k}') # 1,2,4,8,16,32,64,128
# Practical use: creating bitmasks
def bit_mask(k):
return 1 << k
print(f'\nBitmask for bit 0: {bin(bit_mask(0))}') # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}') # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}') # 10000000
# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}') # 1024Högerskift: dividera med tvåpotenser
Högerskiftsoperatorn (>>) skiftar alla bitar åt höger med k positioner och tar bort de k högra bitarna. Detta motsvarar heltalsdivision med 2^k. Pythons högerskift är alltid aritmetiskt: de vänstra bitarna fylls med teckenbiten (0 för positiva tal, 1 för negativa).
Ett vanligt intervjutrick är att extrahera bit k ur talet n med (n >> k) & 1. Detta skiftar bit k ned till position 0 och maskerar bort alla andra bitar. Det är det tydligaste sättet att kontrollera en specifik bit utan att behöva beräkna och jämföra en fullständig mask.
# Right shift = integer division by 2^k
n = 64
for k in range(7):
print(f'{n} >> {k} = {n >> k}') # 64,32,16,8,4,2,1
# Extract bit k from n
def get_bit(n, k):
return (n >> k) & 1
n = 0b10110101 # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
print(f' Bit {k}: {get_bit(n, k)}')
# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}') # -4 (fills with sign bit 1)Snabbguide över praktiska bittrick
Här är en samling av de vanligaste idiomen inom bitmanipulering som ni kommer att stöta på under intervjuer. Lär er dessa mönster utantill – de återkommer i dussintals problem:
n & 1— kontrollera om n är uddan & (n-1)— rensa den lägsta satta bitenn & -n— isolera den lägsta satta bitenn | (1 << k)— sätt bit kn & ~(1 << k)— rensa bit kn ^ (1 << k)— växla bit k(n >> k) & 1— kontrollera bit k
# Bit trick cheatsheet — all at once
n = 0b10110100 # 180
print(f'n = {bin(n)} = {n}')
print(f'n & 1 (odd check) = {n & 1}') # 0: even
print(f'n & (n-1) (clear lowest bit) = {bin(n & (n-1))}')
print(f'n & -n (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1) (set bit 1) = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2) = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5) (toggle bit 5) = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1 (check bit 4) = {(n>>4) & 1}')Räkna satta bitar (popcount)
Att räkna antalet 1-bitar i ett heltal kallas population count (popcount). Den naiva metoden går igenom alla bitar. Brian Kernighans trick är snabbare: rensa upprepade gånger den lägsta satta biten med n &= n - 1 och räkna iterationerna tills n blir 0. Varje iteration tar bort exakt en 1-bit, så loopen körs exakt så många gånger som det finns 1-bitar.
Python 3.10+ tillhandahåller int.bit_count(), som returnerar antalet direkt. För äldre versioner är Kernighans trick standardmetoden vid manuell implementering. Tekniken löser också problemet 'Hamming Weight' på LeetCode.
# Method 1: naive O(log n)
def count_bits_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Method 3: Python built-in (3.10+)
# n.bit_count()
for x in [0, 1, 7, 255, 180, 1024]:
naive = count_bits_naive(x)
fast = count_bits_fast(x)
print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')Bitmanipulering i Python: viktiga fallgropar
Till skillnad från C/Java är Python-heltal godtyckligt stora — det finns inget spill för 32 eller 64 bitar. Det innebär att ni måste maskera resultat manuellt till en fast bredd när ni löser problem som förväntar sig 32-bitarsbeteende: använd & 0xFFFFFFFF för att behålla endast de lägsta 32 bitarna.
NOT-operatorn ~n i Python returnerar -(n+1), inte den bitinverterade version som ni kanske förväntar er från C. För 32-bitarsproblem använder ni ~n & 0xFFFFFFFF eller beräknar 0xFFFFFFFF ^ n för att få det förväntade 32-bitarskomplementet. Dessa skillnader ställer till det för många kandidater som är vana vid bitmanipulering i C-stil.
# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}') # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290
# No integer overflow in Python
big = 1 << 100 # 2^100: huge number, no overflow
print(f'2^100 = {big}') # works fine
# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}') # -1 (all ones shifted in)
# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32 # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}') # 3Skiftoperatorer och multiplikation
Vänster- och högerskift ger ett extremt snabbt sätt att multiplicera eller dividera med tvåpotenser. På hårdvara utförs bitskift med en enda instruktion, medan multiplikation och division kräver flera klockcykler. I Python är heltalsmultiplikation redan effektiv, men förståelsen av sambandet hjälper er att se bitmönster tydligare.
En användbar identitet är att ni kan kontrollera om n är en multipel av 2^k med (n & (2^k - 1)) == 0. Masken 2^k - 1 har alla de k lägsta bitarna satta till 1; AND med den ger resten vid division med 2^k. Detta motsvarar n % (2^k), men är snabbare i C-baserade språk.
# Shift vs arithmetic equivalence
for k in range(1, 5):
n = 48
print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
print()
# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
mask = (1 << k) - 1 # 2^k - 1: lower k bits all 1
return (n & mask) == 0
for n in [16, 24, 32, 15, 100]:
print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')Snabbtest
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde ni er: AND maskerar bitar, OR sätter bitar, XOR växlar bitar och upptäcker skillnader, NOT inverterar (ger -(n+1) i Python), och skift multiplicerar/dividerar med potenser av två, n & (n-1) rensar den lägsta satta biten och ligger till grund för kontroller av tvåpotenser och biträkning, samt Python har ingen overflow med fast bredd, så 32-bitarsproblem kräver uttrycklig maskering med & 0xFFFFFFFF. Nästa steg är att utforska XOR:s självinversa egenskap för att lösa problemfamiljen med ett enda tal.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar” gratis?
Ja – hela texten till ”Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar”?
Repetera alla sex bitvisa operatorer med sanningstabeller och Python-exempel och förstå hur vänster- och högerskiftning motsvarar multiplikation respektive division med två. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Bitvisa operatorer: AND, OR, XOR, NOT och skiftningar
- Single Number och XOR-egenskaper
- Bitmasker: sätt, rensa, växla och kontrollera
- Räkna bitar, hitta saknat tal och vänd bitar