vogel's blog

By vogel, 3 years ago, translation, In English,

Now I am writing an article about bit manipulation, bit magic and other trciks for wiki — conspects (This is a great resource of algorithms in Russian). If you know some useful bit tricks, which used in algoritms or just funny things connected with bits write them in comments below. Also you are welcomed with really strange, weird and sophisticated solutions for well-known problems. For example: swapping values with XOR.

Good style for your comments:

  • Descripotion of the problem
  • Solution of the problem in code with short explanation for tricky moments

Example of a perfect comment:
Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here 

f = (v & (v - 1)) == 0;

Short explanation: Let v — power of two (this is one and k zeros in binary presentation) and v — 1 is k ones in binary presenation. Then notice that bitwise AND v and v — 1 must be 0.

Warm — up problem: Find smallest 1 — bit (not zero) in O(1)

 
 
 
 
  • Vote: I like it  
  • +50
  • Vote: I do not like it  

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Zero is not a power of two. Your code says otherwise :)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

or:
f = __builtin_popcount(v) == 1;

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Smallest bit set to 1 of an integer

int bit = number & -number;

Explanation: -number representation using 2-complement keeps the smallest 1-bit and inverts the other most significative bits.

Unsetting the smallest 1-bit of an integer

int number = 123; number -= number & -number;

Counting the number of bits set to 1

int amount = 0;
for (; number > 0; number -= number & -number)
  ++amount;

Toggle bit i from 1->0 or 0->1

number ^= 1 << i;

Xor with bit set to 1, makes it change its value, whereas the other bits are 0 and don't change anything.

Iterate all subsets of a bitmask in increasing order

for ( int sub = 0 ; sub = sub - bitmask & bitmask ; ) {
  // do something
}

Iterate all subsets of a bitmask in decreasing order

for(int sub = (mask-1) & bitmask ; sub > 0 ; sub = (sub-1) & bitmask )  {
  // do something 
}
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u plz give a small example for "Iterate all subsets of a bitmask in increasing order". It is not clear to me... :/

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Got it.

»
3 years ago, # |
Rev. 12   Vote: I like it -37 Vote: I do not like it

Swap two integers

a ^= b ^= a ^= b;

Check whether two integers are equal or not:

if (a ^ b) // they aren't equal!

Check if a equals -1 or not

if (~a) // a != -1

Get the largest number I can!

int (or long long) INF = -1ull/2;

For the least number

int (or long long) LEAST = ~(-1ull/2);
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Operation x & (x — 1) sets rightmost 1 to 0. As powers of 2 have only one 1 — it can be used to check them.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    And in addition to that, as sugested by K&R in their book, you can use it to count set bits faster than going through all bits checking their states:

    int c; /* counter for bits set in unsigned variable x */
    for(c=0; x; x&=(x-1)) ++c;
    

    Although I've only used it for unsigneds.

»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

I think this one is pretty standard for programming contests, however:

If you wish to swap to enumerable variables' values and can't afford a temporary variable (say you're working on embed software for legacy machines, for an example) than...

int x, y;
/* get values and preprocess whatever you wish... */
x ^= y ^= x ^= y;
/* values swapped, keep going */

Specially handy for old micro-controllers with very little cache

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My favorite is binary searching by bit manipulation — no off-by-1 errors!

/**
   * Binary search by bit toggling from MSB to LSB
   * O(64) bit-wise operations for Longs (O(32) for Ints)
   *
   * @return Some(x) such that x is the largest number for which f is true
   *         If no such x is found, None
   */
  def bitBinSearch(f: Long => Boolean): Option[Long] = {
    var p = 0L
    var n = Long.MinValue
    var t = n >>> 1
    while (t > 0) {
      if (f(p|t)) p |= t
      if (f(n|t)) n |= t
      t >>= 1
    }
    Seq(p, n) find f
  }

Original source: https://github.com/pathikrit/scalgos/tree/master/src/main/scala/com/github/pathikrit/scalgos

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Your expression is like — "Look I've Too Simple and shortest code,

    def bitBinSearch(f:Long=>Boolean):Option[Long]={var p=0L var n=Long.MinValue var t=n>>>1 while(t>0){if(f(p|t))p|=t if(f(n|t))n|=t t>>=1}Seq(p,n)find f}"
    

    Translate it in c++ for others...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain please what Seq(p, n) find f means?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +4 Vote: I do not like it

      p and n are numbers in [0, Long.MaxValue] and [Long.MinValue, 0] respectively for which f maybe satisfactory. Seq(p, n) creates a sequence of these 2 numbers and Seq(p, n) find f returns the first one for which f is true else None. I am using Scala as my language; here's a Java/C++-ish version (not tested):

      long p = 0L, n = Long.MinValue;
      for (long t = n >>> 1; t > 0; t >>= 1) {
        if (f(p|t)) p |= t;
        if (f(n|t)) n |= t;
      }
      if (f(p)) return p;
      if (f(n)) return n;
      return null;
      
»
3 years ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it
  1. n = n * 2 :: n = n << 1
  2. n = n /2 :: n = n >> 1
  3. If x is max power of 2 dividing n, then x = (n & -n)
  4. Total number of bits which are set in **n = __builtin_popcount(n)**
  5. Setting xth bit of n :: n |= (1<<x)
  6. Checking if xth bit of n is set :: checking if n&(1<<x) is non zero
»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone provide links to the problems, where you need a fast way to count number of 1's in mask or index of last setted bit?