bit programming techniques

we going to see simple formulas which makes life easy using bit programming

Truth table:

Logic 1: to check number is even or odd

Number is divisible by 2

 /*Masking the LSB 0000 0001. decimal value = 1*/
if ((x & 1) == 0) {
  x is even
}
else {
  x is odd
}

Number is divisible by 4 

/*Masking the LSB 0000 0011. decimal value = 3*/
if ((x & 3) == 0) {
  x is divisible by 4
}
else {
  x is not divisible  by 4
}

Number is divisible by 8

/*Masking the LSB 0000 0111. decimal value = 7*/
if ((x & 7) == 0) {
  x is divisible by 8
}
else {
  x is not divisible  by 8
}

Number is divisible by 16

/*Masking the LSB 0000 1111. decimal value = 15*/
if ((x & 15) == 0) {
  x is divisible by 16
}
else {
  x is not divisible  by 16
}

Number is divisible by 32

/*Masking the LSB 0001 1111. decimal value = 31*/
if ((x & 31) == 0) {
  x is divisible by 32
}
else {
  x is not divisible  by 32
}

Number is divisible by 64

/*Masking the LSB 0011 1111. decimal value = 63*/
if ((x & 63) == 0) {
  x is divisible by 64
}
else {
  x is not divisible  by 64
}

Number is divisible by 128
 

/*Masking the LSB 0111 1111. decimal value = 127*/
if ((x & 239) == 0) {
  x is divisible by 128
}
else {
  x is not divisible  by 128
}



Logic 2: test nth bit of any number

if (x & (1<<n)) {
  n-th bit is set
}
else {
  n-th bit is not set
}

or

To check a bit, shift the number x to the right, then bitwise AND it:

bit = (number >> x) & 1;

Logic 3:  set the nth bit of given number

y = x | (1<<n)

Logic 4: unset the nth bit of given number

y = x & ~(1<<n)

Logic 5: Toggle the n-th bit. (or just do opposite. if upper then lower  or if lower then upper)

y = x ^ (1<<n)

Main source:  http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/


Logic 6: Multiplication and division

expr1 << expr2 (2 * 4 == 2 << 2) 

is equivalent to multiplication by 2expr2

expr1 >> expr2  (8 / 4 == 8 >> 2)
is equivalent to division by 2expr2 
Logic 7 : check whether the number is power of 2 or not:

 If we subtract a power of 2 numbers by 1 then all unset bits after the only set bit become set; and the set bit become unset.

For example for 4 ( 100) and 16(10000), we get following after subtracting 1
3 –> 011
15 –> 01111
So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become n& (!n&(n-1))

#include<stdio.h> 
#define bool int 

/* Function to check if x is power of 2*/ 
bool isPowerOfTwo (int x) 
{ 
/* First x in the below expression is for the case when x is 0 */ 
return x && (!(x&(x-1))); 
} 
/*Driver program to test above function*/ 
int main() 
{ 
isPowerOfTwo(31)? printf("Yes\n"): printf("No\n"); 
isPowerOfTwo(64)? printf("Yes\n"): printf("No\n"); 
return 0; 
} 

Logic 1: to check number is even or odd
Logic 1: to check number is even or odd
Logic 1: to check number is even or odd
Logic 1: to check number is even or odd
Logic 1: to check number is even or odd


logic 1: explanation:

    01100010
&   00000001
    --------
    00000000

logic 2 : exp

1         00000001    (same as 1<<0)
1<<1      00000010
1<<2      00000100
1<<3      00001000
1<<4      00010000
1<<5      00100000
1<<6      01000000
1<<7      10000000 

logic 3 : exp

    01111000    (120 in binary)
|   00000100    (1<<2)
    --------
    01111100 

Reference:

https://www.quora.com/How-do-you-set-clear-and-toggle-a-single-bit-in-C

https://www.hackerearth.com/practice/notes/bit-manipulation/

http://see-programming.blogspot.in/2013/07/c-program-to-set-reset-check-clear-and.html

logic 7: size of int and int long

[tselva@xxx]$ cat size_int_long.c

#include <inttypes.h>

#include <stdio.h>



int main() {

  printf( "    short int: %zd\n" , sizeof(short int) ) ;

  printf( "          int: %zd\n" , sizeof(int) ) ;

  printf( "     long int: %zd\n", sizeof(long int) ) ;

  printf( "long long int: %zd\n", sizeof(long long int) ) ;

  printf( "       size_t: %zd\n", sizeof(size_t) ) ;

  printf( "        void*: %zd\n\n", sizeof(void *) ) ;





  printf( "PRIu32 usage (see source): %"PRIu32"\n" , (uint32_t) 42 ) ;

  return 0;

}



[tselva@xxxx]$ ./a.out

    short int: 2

          int: 4

     long int: 4

long long int: 8

       size_t: 4

        void*: 4



PRIu32 usage (see source): 42

logic 9: why do we need L,UL representaion

what is meant by UL represenation?

var |= (1UL << 5); // note the brackets to force shift before ORing

1UL - UL represents unsigned long i.e. 32 bit representation of 1



point 1:

A decimal number like -1,1,2,12345678, etc. without any suffix will get the smallest type it will fit, starting with int, long, long long.

An octal or hex number like 0, 0123, 0x123, 0X123 without any suffix will get the smallest type it will fit, starting with int, unsigned, long, unsigned long, long long, unsigned long long.

Point 2:

Because numerical literals are of typicaly of type int. The UL/L tells the compiler that they are not of type int, e.g. assuming 32bit int and 64bit long
long i = 0xffff;
long j = 0xffffUL;

Here the values on the right must be converted to signed longs (32bit -> 64bit)

The "0xffff", an int, would converted to a long using sign extension, resulting in a negative value (0xffffffff)
The "0xffffUL", an unsigned long, would be converted to a long, resulting in a positive value (0x0000ffff)


Ref: https://stackoverflow.com/questions/25605777/c-literal-suffix-u-ul-problems

https://stackoverflow.com/questions/13134956/what-is-the-reason-for-explicitly-declaring-l-or-ul-for-long-values