CODEWITHSUNDEEP
pythonbit-manipulation
NedStarkOfWinterfell
NedStarkOfWinterfell

Reputation: 5153

How to invert alternate bits of a number

The problem is how to invert alternate bits of a number, starting from the LSB. Currently what I am doing is first doing a

count = -1
while n:
   n >>= 1
   count += 1

to first find the position of the leftmost set bit, then running a loop to invert every alternate bit:

i = 0
while i <= count:
 num ^= 1<<i
 i += 2

Is there a quick hack solution instead of this rather boring loop solution? Of course, the solution can't make any asumption about the size of the integer.

Upvotes: 2

Views: 1597

Answers (4)

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8711

The previous one-liner solution,

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

is an O(lg n) solution, where n is the input number. The asymptotically-much-faster solution shown below runs in time O(lg(lg n)), that is, in time proportional to the log of the number of bits in the input number. Note, the binary search as shown worked ok in tests, but perhaps can be improved.

Edit: The expression -1<<L is a mask with its high bits set and its L low bits clear. For example, python displays 255 as the value of (-1<<8)&255, and 256 as the value of (-1<<8)&256. The program begins by doubling L (leaving more and more low bits clear) until L exceeds the number of bits in the number v; that is, until (-1<<L)&v is zero. At each doubling of L, it can move R up. The program then uses binary search, repeatedly halving the L-R difference, to find L=R+1 such that v&(-1<<L) == 0 and v&(-1<<R) > 0, to establish that v is L bits long. Later, the program doubles the length of an alternating-bits mask k until it is at least L bits long. Then it shifts the mask by one bit if L is odd. (Instead of if L & 1: k = k<<1 it could say k <<= L&1. Note, I interpreted “alternate bits” as beginning with the bit just below the MSB. To instead always toggle bits 0,2,4..., remove the if L & 1: k = k<<1 line.) Then it picks off the low L bits of k by &'ing with (1<<L)-1, ie, with (2**L)-1. Note, the program's O(lg(lg n)) time bound depends on O(1) logical operations; but as L gets large (beyond a few hundred bits), 1<<L etc become O(lg n) operations.

def clearaltbits(v):
    if not v:
        return 0
    L, R = 16, 0
    # Find an upper bound on # bits
    while (-1<<L) & v:
        R, L = L, 2*L
    # Binary search for top bit #
    while not (-1<<L) & v:
        m = (L+R)/2
        if (-1<<m) & v:
            R = m
        else:
            L = m
        if L==R+1: break
    print bin(v),'has',len(bin(v))-2,'bits.'
    # Make big-enough alternate-bits mask
    k, b = 0b0101010101010101, 16
    while not (-1<<L) & k:
        k = (k<<b)|k
        b += b
    if L & 1:
        k = k<<1
    k = k & ((1<<L)-1)
    print bin(k^v),'fin'


clearaltbits(3**3)
clearaltbits(5**6)
clearaltbits(7**17)
clearaltbits(13**19)

The output from the four function calls is shown below.

0b11011 has 5 bits.
0b10001 fin

0b11110100001001 has 14 bits.
0b10100001011100 fin

0b110100111001001110000011001001100110111010000111 has 48 bits.
0b100001101100011011010110011100110011101111010010 fin

0b10011110100000000111000001101101000001011000100011000010010000111010101 has 71 bits.
0b11001011110101010010010100111000010100001101110110010111000101101111111 fin

Upvotes: 2

martineau
martineau

Reputation: 123463

This will work for any length positive integer:

def invert_alt_bits(n):
    m = 1
    while True:
        n ^= m
        m <<= 2
        if m > n: break
    return n

Upvotes: 0

schesis
schesis

Reputation: 59128

Expanding on the answer trideceth12 gave - here's a one-liner that calculates and applies the mask:

n ^ sum(2**i for i in range(0, len(bin(n))-2, 2))

... assuming you do want to start at the LSB, that is.

Or if you're starting at the most significant set bit:

n ^ sum(2**i for i in range(len(bin(n))-3, -1, -2))

Upvotes: 1

jsj
jsj

Reputation: 9391

I think this might work:

A bitwise XOR with an alternating mask 10101010...10 should invert every other bit.

If you want to invert alternating bits in `0011', the following table shows the result:

i | m | i XOR m
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

In python XOR is achieved with i ^ m. Of course you would have to determine the literal value of your mask too, this would depend on the size of your i number.

Upvotes: 5

Related Questions