Mis-conceptions with Bitwise operators

“Bitwise operations are really important in all kinds of embedded systems.. and the things that you do are all on base 2. mostly, these operators are not used much in application programming.. But very useful for systems & memory optimized programs.!! If you write algorithms to save memory, knowing bitwise is a must”

Introduction
    Let’s start with ground basics for binary..
   In a 32-bit binary, you should know that, based on the location of the 1 in it, 2^n varies..
That is, 0000 0001 – 2^0                0000 0100 - 2^2             0001 0000 - 2^4
            0000 0010 – 2^1                 0000 1000 - 2^3             0010 0000 - 2^5
So, the series is like 1, 2, 4, 8, 16,.. The in-between numbers permute. i.e, 2->4.. If you take the count of numbers between these, you will get a series, 0, 1, 3, 7, 9, 15… 
This is how mapping between a binary and a decimal is done.. hexadecimal number is just the grouping of 4-bits..  that is, < 2^4..
With all these bits, you can do logical bitwise operations, AND, OR, NOT, XOR.
Concepts

• OR – its used for masking. In a embedded system, there will be a 32-bit status register. To set or turn on a flag in this 32-bit, you will use a mask and | it with the already existing status bit.
• AND – its used for verifying whether a particular bit is set. mostly used to check whether a particular status bit is set in the register
• XOR – its for toggling the bits. used for set/reset!!.. only if you have different bits, you get 1. otherwise, its all zero. that’s why, it can convert 1 –> 0 and if 0 is there then 1.
• NOT – mostly for turning off a flag.

If you have a 8-bit flag. Then you get the following constants defined,

static final int flagAllOff = 0;  //         000...00000000 (empty mask)
static final int flagbit1 = 1;    // 2^^0    000...00000001
static final int flagbit2 = 2;    // 2^^1    000...00000010
static final int flagbit3 = 4;    // 2^^2    000...00000100
static final int flagbit4 = 8;    // 2^^3    000...00001000
static final int flagbit5 = 16;   // 2^^4    000...00010000
static final int flagbit6 = 32;   // 2^^5    000...00100000
static final int flagbit7 = 64;   // 2^^6    000...01000000
static final int flagbit8 = 128;  // 2^^7    000...10000000

Example, Now, take a integer status register(statusreg) with all 0.

1. Set bit-3,7 in the status register (using OR)

   statusreg |= flagbit3

   statusreg |= flagbit7

2. test whether bit-7 is set or not, (using AND)

    if((statusreg & flagbit7) == flagbit7)  // bit 7 is set

3. toggle bit-5, (using XOR)

   statusreg ^= flagbit5

4. set the bit-5 to zero. Using NOT, AND operator

   statusreg & ~flagbit5

5. combining masks using OR. set bit 5 and 6.

   statusreg & (flagbit5 | flagbit6)

6. XOR has a special property.. if u XOR same number, you get zero. 

  i.e, a = 01010011.. a ^ a = 0

5. Using the above principle for swapping. :)

a ^= b; // a = a^b
b ^= a; // b = b^a^b = a
a ^= b; // a = a^b^a = b

6. Extract just 8-bits from a value,

    ch &= 0xFF

More operations & More use-cases

   Left shift & right shift. Now, it should be clear that the number of left shifts you do, 

you multiple more 2 to the number. The more right shifts you do, you divide number by 2.

Left shift – Add 0 to the right side.

Right shift – Add 0 to the left side.

All permissions even on applications are maintained with bits to easily understand it.

Errors caused till now on the articles

The major bitwise we misused is, 

http://analgorithmaday.blogspot.com/2011/04/unique-items-in-array.html

You cannot get the unique items in the array if the numbers are greater than 32. And, for negative numbers, its only 31 numbers. 

Since we use the position of 1’s to get the duplicate.  But it works well for strings, because there is no character which will round and overlap with the same bit.

i.e, if in an array, you have integers like, {90, 26, 7, 2}

and you want to check whether duplicates are there in this using the logic we discussed in the above link, for 90, you get the bit set @26. Now the next integer in array also sets bit at 26.. this will make 90 & 26 duplicate :)

This is the loophole !!.. Thanks to my friend who worked on optimizing RSA algorithm for  pointing out this mistake.. :D

Even longest string check won’t work!!.. :).. It will work only if you have lower case letters and you subtract the ASCII value with ‘a’.. So you will get only values within 26. :D

The below links are all wrong: :D

http://analgorithmaday.blogspot.com/2011/05/finding-longest-substring-in-string.html

http://analgorithmaday.blogspot.com/2011/04/unique-items-in-array.html

finding longest substring will work only if the duplication doesn’t collide.

We will see more about collisions soon.. With HASH TABLES.. :D