0Pricing
Coding Interview Prep · Leçon

Opérateurs bit à bit : AND, OR, XOR, NOT et décalages

Passez en revue les six opérateurs bit à bit avec des tables de vérité et des exemples Python, puis comprenez comment les décalages à gauche et à droite correspondent à une multiplication et une division par deux.

Opérateurs bit à bit : AND, OR, XOR, NOT et décalages est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Pourquoi la manipulation des bits est importante

La manipulation des bits permet d’agir directement sur la représentation binaire des entiers. De nombreux problèmes qui semblent complexes deviennent triviaux grâce à la bonne astuce de manipulation des bits : trouver un nombre manquant en O(n) avec un espace O(1), échanger des variables sans variable temporaire ou encoder des sous-ensembles de manière compacte. Les personnes qui mènent les entretiens utilisent ces problèmes pour évaluer votre compréhension du fonctionnement de bas niveau et votre créativité.

Les entiers Python ont une précision arbitraire — ils peuvent être aussi grands que la mémoire le permet — mais les opérations sur les bits suivent toujours la sémantique standard du complément à deux au niveau matériel. Les six opérateurs agissent bit par bit sur les représentations binaires des entiers.

# 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 = 5

Opérateur AND : masquage des bits

L’opérateur AND (&) renvoie 1 uniquement lorsque les deux bits d’entrée valent 1. Il sert principalement au masquage : sélectionner certains bits d’un nombre tout en mettant tous les autres à zéro. Pour vérifier si le bit k est activé dans le nombre n, évaluez n & (1 << k) — si le résultat est non nul, le bit k vaut 1.

AND sert également à effacer le bit activé de poids faible : n & (n - 1) supprime le bit 1 le plus à droite. Cette technique permet de compter efficacement les bits activés et de vérifier si un nombre est une puissance de deux (une puissance de deux possède exactement un bit activé, donc 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}')

Opérateur OR : activer des bits

L’opérateur OR (|) renvoie 1 si au moins un bit d’entrée vaut 1. Il sert principalement à activer un bit spécifique à 1 sans modifier les autres. Pour activer le bit k du nombre n, utilisez n | (1 << k). Le 1 décalé jusqu’à la position k active ce bit ; tous les autres bits restent inchangés, car tout élément combiné avec 0 par OR reste identique.

OR sert également à combiner des indicateurs : si vous représentez les indicateurs de fonctionnalité par des bits individuels, vous pouvez en activer plusieurs avec OR. Par exemple, READ | WRITE | EXECUTE combine trois bits d’autorisation en un seul entier.

# 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)}')

Opérateur XOR : inversion et différence

L’opérateur XOR (^) renvoie 1 lorsque les bits d’entrée diffèrent. XOR possède trois propriétés algébriques puissantes : a ^ a = 0 (des entrées identiques s’annulent), a ^ 0 = a (zéro est l’élément neutre), et XOR est à la fois commutatif et associatif. Ces propriétés font de XOR l’outil de choix pour trouver des éléments uniques.

XOR sert également à inverser un bit spécifique : n ^ (1 << k) inverse le bit k tout en laissant les autres inchangés. Si le bit k valait 0, il devient 1 ; s’il valait 1, il devient 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=7

Opérateur NOT et complément à deux

L’opérateur NOT (~) inverse tous les bits. En Python, ~n est égal à -(n+1) en raison de la représentation en complément à deux. Cela surprend beaucoup de personnes : ~5 = -6, et non 0b11111010 comme on pourrait naïvement s’y attendre. Les entiers Python ont une précision infinie ; inverser tous les bits d’un nombre positif produit donc un résultat négatif en complément à deux.

En pratique, vous utilisez rarement ~ seul en Python pour manipuler les bits. Utilisez-le plutôt avec AND pour effacer certains bits, ou calculez ~n & mask lorsque mask limite la largeur à un nombre précis de bits (par exemple, & 0xFFFFFFFF pour 32 bits).

# 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 ones

Décalage à gauche : multiplication par des puissances de deux

L’opérateur de décalage à gauche (<<) décale tous les bits vers la gauche de k positions et remplit de zéros les positions libérées à droite. Cela revient à multiplier par 2^k. Un décalage à gauche de 1 double la valeur ; un décalage de k la multiplie par 2^k.

Dans les problèmes d’entretien, les décalages à gauche servent le plus souvent à créer des masques de bits : 1 << k crée un nombre dont seul le bit k est activé. C’est le fondement de toutes les opérations de manipulation des bits : activer, effacer, inverser et vérifier des bits individuels commence par 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}')  # 1024

Décalage à droite : division par des puissances de deux

L’opérateur de décalage à droite (>>) décale tous les bits vers la droite de k positions et supprime les k bits les plus à droite. Cela revient à effectuer une division entière par 2^k. Le décalage à droite de Python est toujours arithmétique : les bits les plus à gauche sont remplis avec le bit de signe (0 pour un nombre positif, 1 pour un nombre négatif).

Une astuce courante en entretien consiste à extraire le bit k du nombre n avec (n >> k) & 1. Cela décale le bit k jusqu’à la position 0 et masque tous les autres bits. C’est la manière la plus claire de vérifier un bit précis sans devoir calculer et comparer un masque complet.

# 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)

Aide-mémoire des astuces pratiques sur les bits

Voici un ensemble des expressions idiomatiques les plus courantes de manipulation des bits que vous rencontrerez en entretien. Mémorisez ces modèles : ils apparaissent régulièrement dans des dizaines de problèmes :

  • n & 1 — vérifier si n est impair
  • n & (n-1) — effacer le bit activé de poids faible
  • n & -n — isoler le bit activé de poids faible
  • n | (1 << k) — activer le bit k
  • n & ~(1 << k) — effacer le bit k
  • n ^ (1 << k) — inverser le bit k
  • (n >> k) & 1 — vérifier le 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}')

Comptage des bits activés (comptage de population)

Le comptage du nombre de bits 1 dans un entier s’appelle le comptage de population. L’approche naïve parcourt tous les bits. L’astuce de Brian Kernighan est plus rapide : elle efface répétitivement le bit activé de poids faible avec n &= n - 1, en comptant les itérations jusqu’à ce que n devienne égal à 0. Chaque itération supprime exactement un bit 1 ; la boucle s’exécute donc exactement autant de fois qu’il y a de bits 1.

Python 3.10+ fournit int.bit_count(), qui renvoie directement le nombre de bits. Pour les versions antérieures, l’astuce de Kernighan est l’approche manuelle standard. Cette technique permet également de résoudre le problème « poids de Hamming » sur 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}')

Manipulation des bits en Python : pièges importants

Contrairement à C/Java, les entiers Python sont arbitrairement grands : il n’y a pas de dépassement de capacité sur 32 ou 64 bits. Vous devez donc masquer manuellement les résultats sur une largeur fixe lorsque vous résolvez des problèmes qui attendent un comportement sur 32 bits : utilisez & 0xFFFFFFFF pour ne conserver que les 32 bits de poids faible.

L’opérateur NOT ~n en Python renvoie -(n+1), et non la version dont les bits sont inversés à laquelle vous pourriez vous attendre en C. Pour les problèmes sur 32 bits, utilisez ~n & 0xFFFFFFFF ou calculez 0xFFFFFFFF ^ n afin d’obtenir le complément 32 bits attendu. Ces différences déconcertent de nombreux candidats habitués à la manipulation des bits à la manière du langage C.

# 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}')  # 3

Opérateurs de décalage et multiplication

Les décalages à gauche et à droite permettent de multiplier ou de diviser très rapidement par des puissances de deux. Sur le matériel, les décalages de bits sont des opérations exécutées en une seule instruction, tandis que la multiplication et la division nécessitent plusieurs cycles. En Python, la multiplication entière est déjà efficace, mais comprendre cette relation vous aide à mieux visualiser les motifs binaires.

Une relation utile : pour vérifier si n est un multiple de 2^k, utilisez (n & (2^k - 1)) == 0. Le masque 2^k - 1 possède tous ses k bits de poids faible activés ; lui appliquer AND donne le reste de la division par 2^k. C’est équivalent à n % (2^k), mais plus rapide dans les langages basés sur C.

# 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)}')

Vérification rapide

Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation abordés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : AND masque les bits, OR active les bits, XOR inverse les bits et détecte les différences, NOT inverse les bits (et produit -(n+1) en Python), tandis que les décalages multiplient ou divisent par des puissances de deux, n & (n-1) efface le bit activé de poids faible et constitue la base des vérifications de puissances de deux et du comptage des bits, et Python n’a pas de dépassement de capacité sur une largeur fixe ; les problèmes sur 32 bits nécessitent donc un masquage explicite avec & 0xFFFFFFFF. Nous allons ensuite explorer la propriété d’inverse propre à XOR pour résoudre la famille de problèmes du nombre unique.

Questions Fréquemment Posées

La leçon « Opérateurs bit à bit : AND, OR, XOR, NOT et décalages » est-elle gratuite ?

Oui — le texte complet de « Opérateurs bit à bit : AND, OR, XOR, NOT et décalages » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Opérateurs bit à bit : AND, OR, XOR, NOT et décalages » ?

Passez en revue les six opérateurs bit à bit avec des tables de vérité et des exemples Python, puis comprenez comment les décalages à gauche et à droite correspondent à une multiplication et une divi… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Opérateurs bit à bit : AND, OR, XOR, NOT et décalages » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Opérateurs bit à bit : AND, OR, XOR, NOT et décalages
  2. Nombre unique et propriétés de XOR
  3. Masques binaires : définir, effacer, inverser et vérifier
  4. Compter les bits, nombre manquant et inversion des bits
← Retour à Coding Interview Prep