42

I have an integer with a value 7 (0b00000111) And I would like to replace it with a function to 13 (0b00001101). What is the best algorithm to replace bits in an integer?

For example:

set_bits(somevalue, 3, 1) # What makes the 3rd bit to 1 in somevalue?
martineau
  • 119,623
  • 25
  • 170
  • 301
Váradi Norbert
  • 429
  • 1
  • 4
  • 3

4 Answers4

71

These work for integers of any size, even greater than 32 bit:

def set_bit(value, bit):
    return value | (1<<bit)

def clear_bit(value, bit):
    return value & ~(1<<bit)

If you like things short, you can just use:

>>> val = 0b111
>>> val |= (1<<3)
>>> '{:b}'.format(val)
'1111'
>>> val &=~ (1<<1)
'1101'
Kos
  • 70,399
  • 25
  • 169
  • 233
  • Why not simply "value - (1 << bit)" to clear bit? – bikram Nov 10 '22 at 09:12
  • 2
    Idempotency - Subtraction will affect other bits if given bit is already cleared; bitwise operations won't touch other bits at all – Kos Nov 11 '22 at 21:51
50

You just need:

def set_bit(v, index, x):
  """Set the index:th bit of v to 1 if x is truthy, else to 0, and return the new value."""
  mask = 1 << index   # Compute mask, an integer with just bit 'index' set.
  v &= ~mask          # Clear the bit indicated by the mask (if x is False)
  if x:
    v |= mask         # If x was True, set the bit indicated by the mask.
  return v            # Return the result, we're done.

>>> set_bit(7, 3, 1)
15
>>> set_bit(set_bit(7, 1, 0), 3, 1)
13

Note that bit numbers (index) are from 0, with 0 being the least significant bit.

Also note that the new value is returned, there's no way to modify an integer "in place" like you show (at least I don't think so).

unwind
  • 391,730
  • 64
  • 469
  • 606
  • 2
    He said, casually, as if thousands of people inexperienced with binary would not have to walk through this code step by step over the years to figure out what the hell it was doing that caused it to work so perfectly. – temporary_user_name Feb 03 '17 at 04:35
  • 1
    @Aerovistae Heh ... Not sure if you're being tongue-in-cheek. I added comments to make the code even clearer. Hopefully that will save all those people some work. :) – unwind Feb 03 '17 at 09:10
  • Thanks! I was indeed being tongue-in-cheek. Had to go totally relearn my binary operations to understand what was going on; hadn't touched 'em since college. – temporary_user_name Feb 03 '17 at 09:25
  • You might be happy to know that _as is_ this works for numpy arrays as well. `v` can be a numpy array and `index` can either be a scalar or a numpy array of the same length as `v`. Very useful! Who knew setting bits needed to be so clever. – John Lunzer Mar 10 '17 at 15:16
  • @SwiftsNamesake I'm sure it can be clevered out, but this makes it pretty clear which was the goal. – unwind Oct 03 '17 at 07:45
  • @SwiftsNamesake would you post a `def set_bit(v, index, x)` implementation without branches? – Kos May 14 '18 at 08:59
11

You can use bitwise opertions. http://wiki.python.org/moin/BitwiseOperators

if you want to set a given bit to 1 you can use bitwise 'or' with 1 on given position:

0b00000111 | 0b00001000 = 0b00001111

to set a given bit to 0 you can use bitwise 'and'

0b00001111 & 0b11111011 = 0b00001011

Note that 0b prefix is for binary numbers and 0x is for hexadecimal.

Priyank Chheda
  • 521
  • 5
  • 16
wmiel
  • 153
  • 5
  • Hi, instead of posting a new answer and deleting the old one, consider just editing your old answer. :-) – sloth Aug 29 '12 at 08:52
  • That was my intention but I had it opened in two tabs and sent from the wrong one :) – wmiel Aug 29 '12 at 08:55
  • But I would like to set bytes by index. – Váradi Norbert Aug 29 '12 at 08:56
  • Then (as @unwind showed you) you can take 0b1 (=1) and shift it left to the correct position (1 << index in his code). Then you can use |, & or calculate inversion, which changes all zeros to ones. – wmiel Aug 29 '12 at 08:59
0

Going by the examples provided, it sounds like you are looking to swap bits in an integer. For example in 7 (0b00000111), if you swap the bits in the 3rd and 1st positions you obtain 13 (0b00001101).

I would have the following as a function signature swap_bits(val, i, j)

What is the best algorithm? Well, the following algorithm takes constant time, O(1).

def swap_bits(val, i, j):
    """
    Given an integer val, swap bits in positions i and j if they differ
    by flipping their values, i.e, select the bits to flip with a mask.
    Since v ^ 1 = 0 when v = 1 and 1 when v = 0, perform the flip using an XOR.
    """
    if not (val >> i) & 1 == (val >> j) & 1:
        mask = (1 << i) | (1 << j)
        val ^= mask
    return val

Example:

 >>> swap_bits(7, 3, 1)
 13

The code leverage bit twiddling tricks and here is a good resource by Sean Anderson. I am working on providing the code snippets in Python here.

Brayoni
  • 696
  • 7
  • 14