Bit level tricks: XOR

Here goes exclusive post for Exclusive-OR / XOR !

XOR is a binary operator which acts on two number like A XOR B, denoted as A ^B.  A ^ B basically tells how different A is from B (or vice-versa). If a bit of A is different from the same bit of B, the resulting bit is 0.

Properties

1.   XOR with itself results 0

XOR-ing a number with itself returns 0. This also goes with the definition that XOR tells how different two numbers are. X ^ X = 0

     00000100   (4 in binary)                     
^   00000100   (4 in binary)
     ------------
     00000000

 

2.   XOR with 0 results number

 XOR-ing with zero gives back the same number.  X ^ 0 = X

     00000100   (4 in binary)                     
^   00000000   (0 in binary)
     ------------
     00000100

 

3.   XOR is associative and cumulative

 XOR is associative as well cumulative.

Associativity:  (X^Y)^Z = X^(Y^Z)

Cumulative:  X^Y = Y^X 

 

Bit Hacks

Let's see some XOR hacks.

#1: Swapping without temp variable

 X = X ^ Y

 Y = X ^ Y

 X = X ^ Y

Let's prove it by taking an example

X = A, Y = B

X = X ^ Y = A^ B

Y = X ^ Y = (A^B)^B = A^(B^B)  

    = A^0 //by property 1

    = A // by property 2

X = X ^ Y = (A^B)^A

    = B^(A^A)

    = B

#2: Check if two numbers have same sign

If two numbers have same sign then the MSB will be same (i.e. either both will be 0 or 1). This means that XOR of that bit will result in zero. 

 X ^ Y --> MSB of both numbers will be 0 if both numbers have same sign.

     00100100   (X)
^   01100011    (Y)
     ------------

     01000111     (>=0)

Above approach can be generalized as 

X ^ Y >= 0 

#3: Toggle between two values of a variable

Change value of a variable between two allowed values. So if the value is A change it to B and vice-versa. 

if X = A

change value of X to B 

XOR properties discussed above helps in achieving this. 

X = A ^ B ^ X

X = A ^ B ^ X

    = A ^ B ^ A   // X = A

    = (A^A)^B

    = B

 ---

keep coding !!!

Bit level tricks: setting and unsetting right most 1 bit

This post is in continuation with the earlier post, where I have discussed some of the bit manipulation techniques. In previous post, I discussed about how to set, unset and toggle a bit at fixed position like 3rd from right/LSB, 1st from left/MSB etc. Setting and unsetting a bit at fixed position is relatively easier to achieve by using left and right shift operators.
 
This post will discuss about manipulating a bit at relative positions, like right most 1 bit, left most 0th bit etc. Here also, I will explain all tricks using 8 bit number.

 

Bit Hacks

#1: Unset the rightmost 1 bit

So objective is to turn off the right most 1 bit in a number.  If input number is 10100100 then it needs to get converted into a number with b2 (b0 is LSB; highlighted bit is b2) getting turn off.

                           X    = 00100100 

                          X-1  = 00100011   

   Expected response = 00100000   ??

As shown above, subtracting 1 from number unsets the right most 1 but it also sets the zeros right to 1. Please note that other bits left of targeted 1 remain unchanged. Can X and X-1 be combined to get the expected response. If you notice closely the last 2 bits, ANDing looks to do the job. 

     00100100   (36 in binary)
&  00100011    (36 -1 )
     ------------
     00100000 

     10000000 (-128 in binary)

&  01111111  (-128 -1 in binary = 127 )

     ------------

     00000000

 

     00000000 (0 in binary; there is no right most bit)

&  11111111  (0 -1 in binary = -1)

     ------------

     00000000  (no change)

General formula for unsetting the right most 1 bit of a number, X

X = X  & (X-1)

Also, be careful of the impact of changing AND to OR in above formula.

#2: Unset all except rightmost 1 bit

So we need to unsets (clears off or changes to 0) all bits except the right most 1 bit. Trivial approach to solve this would be to RIGHT SHIFT the number until you encounter the set bit (i.e. 1) and counting the number of shifts done. 

    while(X & 1 != 0){

        count++;

        X = X>> 1;

    }

 Above approach more easier to think logically but execution complexity and verbosity is high. Let's think of abstracting it into minimal number of steps. 

     00100100   (X = 36;  in binary)
     11011011    (~X )

                +1
     ------------
     11011100  (-X; in two's complement system -X = ~X+1)

Let's use above -X 

     00100100   (X = 36;  in binary)
&  11011100  (-X)
     ------------
     00000100  (bingo!!!)

     10000000   (X = -128;  in binary)
&  10000000  (-X = -128)
     ------------
     10000000  

And it can be generalized as:

X = X  & (~X)

#3: Set the right most 0-bit

So this hack expects to turn on the right most 0 bit (irrespective of position). This also can be achieved by multiple steps but we want to achieve it compactly. 

     00100100   (X = 36;  in binary)

                +1
     ------------
     00100101  (X+1; )

So adding 1 sets up the right most 0. This can be used to set the right most 0 to 1. 

      00100100   (X = 36;  in binary)

  |   00100101   (X+1 )
     ------------
      00100101  

      01110111   (X )

  |   01111000   (X+1 )
     ------------
      01111111

So OR-ing X with X+1 does the job. 

X = X  | (X+1) 

Related Post : Bit manipulation in Java

 Bit level tricks : setting, unsetting and toggling a bit

----

keep coding ! 

Bit level tricks : setting, unsetting and toggling a bit

I will be talking here, about some of the coolest language agnostic bit hacks. Below diagram, gives brief idea about the relative positions of bits in a 1 byte number. Right most bit, 0th is LSB and left most bit, 7th bit is MSB.

Bit operators 

Just as a re-cap, let's start with the list of bit operators. I have discussed about them, here.  I have not included unsigned right shift operator, >>> in below list, as it's specific only to Java.

&  -  Bitwise AND
 |   -  Bitwise OR
^   -  Bitwise XOR
~   -  Bitwise NOT
>> - Bitwise SHIFT LEFT
<< - Bitwise SHIFT RIGHT

Above operators are mostly used for bit level manipulation.

Below table, will be handy to understand the behavior of SHIFT operators. It is used to manipulate a bit a particular position like 3rd, 7th etc. LSB is 0th bit and MSB is 7-th bit (as shown in above diagram as well).

1<<0 or 1  - 00000001
1<<1         - 00000010
1<<2         - 00000100
1<<3         - 00001000
1<<4         - 00010000
1<<5         - 00100000
1<<6         - 01000000

1<<7         - 10000000

Note - index starts from 0.

 

Bit Hacks

Here, we will always consider 8 bit (1 byte) signed numbers to explain all hacks. The same approach can be used for signed number of any size (like 16, 32 bits etc ).

 

#1: Set bit at a position

Setting a bit means, updating its value to 1 (irrespective of the current value). OR-ing a bit with 1 sets the bit ( & OR-ing a bit with 0 leaves it unchanged).

     00000000   (0 in binary)                     
|    00000001    ( 1 or 1 << 0)
     ------------
     00000001


     01001001   (73 in binary)
|    00001000    ( 1<<3)
     ------------
     01001001

General formula for setting n-th bit of a number X

X = X  | 1 <<  n 

#2: Unset bit at a position

To unset a bit, we need to AND it with 0. But the tricky part is that, other bits should be 1 so that the only the target bit gets unset. 

00000001  = 1

11111110   = ~1

     00000001   (1 in binary)                     
&  11111110    ( ~(1<<0)  )
     ------------
     00000000


     01001001   (73 in binary)
&  11110111    ( ~(1<<4)  )
     ------------
     01000001

General formula for unsetting n-th bit of a number X

X = X  & ~(1<< n) 

#3: Toggle a bit

 Toggling a bit means flipping it; i.e. make it 1 if it is 0 and 0 if it is 1. So we need to use something which turns 0 to 1 and 1 to 0. 

Test if the bit is set. 

    - If set, AND it with 0 (to make it 0)

    - if not set, OR it with 1 (to make it 1)

Let's take a case where we want to toggle the MSB of a 8 bit variable, X whose value is -1.

//n = 7

if(X & (1<<n) == 0){

   //nth-bit is set

   X = X & ( 1<< n)

}else{

  //nth-bit is not set

  X= X | (1<<n)

}

Above approach works, but it require multiple operations to toggle a bit. Can it be done using a single step? YES!
Recall that, XOR-ing a bit with 1 will turn it to 0 if it's already 1 and vice-versa.

    01001001   (73 in binary)
^  00001000    ( 1<<3)
     ------------
    01000001 

 It can be generalized as:
 X = X  ^ (1<< n)

---
do post your inputs/feedback.
keep coding !!!

Generate power set of a set

Given a set S, the Power Set (or powerset) denoted as P(S), is set of all subsets of S. [A set is a collection of certain values, without any particular order, and no repeated values] (link)

If S = {a,b,c}
Power Set, P(S) = { {}, {a}, {b},  {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

Power Set is the different ways of selecting items from the given set (including none and all elements).  Also, just like a set, the order doesn't matter in power set. If the number of elements in set in 3 then the number of elements in the power set will be 8 i.e. 2^3.

|S| = n
|P(S)| = 2^n 

Algorithm

One of the simplest algorithms for generating all subsets is Binary Counting (Algorithm Design Manual). This approach uses binary representation to get all subsets. To generate all subsets, we need to count from 0 to 2^n - 1. For each integer, successively mask off each of the bits and compose a subset of exactly the items corresponding to 1 bits. 

Any subset of a set can either contain or not contain an element. So there are two states for each element of the set; either it is present or absent. This can be used to derive the formula of 2^n (i.e. 2.2.2.....n times). Two states for each element of the set can be visualized as true/false or (1/0). If a position is true, the element gets added to the result otherwise ignore it. 

let S = {a,b,c}

counter   subsets

000         {}             //all bits are off; so no element is in subset

001         {a}           // LSB or bit at lowest position is 1, so this means the first element is in subset

010         {b}

011         {a,b}

100         {c}

101         {a,c}

110         {b,c}

111         {a,b,c}     //all bits 1, so all elements make to subset

So from the above table, the list of all subsets will give power set. This approach can be used to generate all subsets of a set programmatically.

Java Implementation

Set can contain any type of element, so to generalize we can select generic numbers which denote the index of the element (but be careful that set doesn't support index-related operations).

S = {apple, orange, mango} 

is equivalent to S ={1,2,3}

so first index = apple

2nd index = orange, and so on.

package hacker;

import java.util.ArrayList;
import java.util.List;

/**
 * Generate power sets of a set. if S = {1,2,3} P(S) =
 * {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} generate method just takes a
 * number like 3 for above case.
 */
public class PowerSet {
 private List<List<Integer>> generate(int num) {
  int size = 1 << num;
  System.out
    .format("Set size is %d, and power set size is %d", num, size);

  List<Integer> result;
  List<List<Integer>> output = new ArrayList<>(size);

  for (int i = 0; i < size; i++) {
   result = new ArrayList<>();
   int t = i;
   int count = 1;

   // values to be added in subset
   while (t > 0) {
    // if LSB is one, add corresponding element
    if ((t & 1) > 0) {
     result.add(count);
    }
    count++;
    // shift right by 1 position; so 100 will become 10
    t = t >> 1;
   }
   output.add(result);
  }
  return output;
 }

 public static void main(String[] args) {
  PowerSet ps = new PowerSet();
  int num = 3; // set has 3 elements
  List<List<Integer>> powerset = ps.generate(num);

  System.out.println("\noutput :" + powerset);
 }
}

Output

Set size is 3, and power set size is 8
output :[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

Important Points

1. Above approach doesn't generate the subset in lexicographic order. It is bit tricky to generate subsets in lexicographic (sorted) order.
2. Above approach can be used to randomly generate a subset.
3. To generate the next or previous subset using the above approach, just increment or decrement the number by one and then convert that into a subset.
4. Above approach can also be used to used to generate subsets of a fixed length or k-elements (k<n).

References
http://www.mathsisfun.com/sets/power-set.html  

---

keep coding !!!