bit programming

- bit position starts from 0 to n and not from 1 to n
- An n-bit integer in that format can store numbers between 

between −(2n−1) to (2n−1)-1 and so  in our case, between -128 and 127.

2n−1−1
1.  how to find whether given number is power of 2
 

if(n && !(n & (n-1))) { number is power of 2 }

note : number is power of 2 is different from number divisible by 2

2. if we right shift the number until it become zero then we will know the left most bit set position by subtracting the 1 from the number of shift

Ref : http://www.geeksforgeeks.org/smallest-power-of-2-greater-than-or-equal-to-n/

    /* If n is a power of 2 then return n */
    1  If (n & !(n&(n-1))) then return n 
    2  Else keep right shifting n until it becomes zero 
        and count no of shifts
        a. Initialize: count = 0
        b. While n ! = 0
                n = n>>1
                count = count + 1

     /* Now count has the position of set bit in result */
    3  Return (1 << count)  



unsigned int nextPowerOf2(unsigned int n)

{

  unsigned count = 0;



  /* First n in the below condition is for the case where n is 0*/

  if (n && !(n&(n-1)))

    return n;



  while( n != 0)

  {

    n  >>= 1;

    count += 1;

  }



  return 1 << count;

}

3. program to check the number of set bits in the given number n

int count_set_bits(unsigned int n)

{

  unsigned count = 0;

  while( n != 0)

  {

    if(n & 1) {

       count += 1;

    }

    n  >>= 1;

  }

  return count;

}

Else the efficient method is below:Beauty of the this solution is number of times it loops is equal to the number of set bits in a given integer. 

   1  Initialize count: = 0
   2  If integer n is not zero
      (a) Do bitwise & with (n-1) and assign the value back to n
          n: = n&(n-1)
      (b) Increment count by 1
      (c) go to step 2
   3  Else return count 

Implementation of Brian Kernighan’s Algorithm:





#include<stdio.h>



/* Function to get no of set bits in binary

   representation of passed binary no. */

unsigned int countSetBits(int n)

{

    unsigned int count = 0;

    while (n)

    {

      n &= (n-1) ;

      count++;

    }

    return count;

}



/* Program to test function countSetBits */

int main()

{

    int i = 9;

    printf("%d", countSetBits(i));

    getchar();

    return 0;

}





Example:

Example for Brian Kernighan’s Algorithm:
   n =  9 (1001)
   count = 0

   Since 9 > 0, subtract by 1 and do bitwise & with (9-1)
   n = 9&8  (1001 & 1000)
   n = 8
   count  = 1

   Since 8 > 0, subtract by 1 and do bitwise & with (8-1)
   n = 8&7  (1000 & 0111)
   n = 0
   count = 2

   Since n = 0, return count which is 2 now.
Ref : http://www.geeksforgeeks.org/count-set-bits-in-an-integer/

how negative number stored in the memory

how to check given number is negative or positive using bit programming

how to find little endian and big endian

write a program to check OS is 32 bit or 64 bit

4. this might help to find the system is 32 bit or 64 bit but not reliable. because depends on the compiler the integer size will vary . But it definitely tells that whether integer is 32 bit long or 64 bit long.

printf("\nsize of the int is %d",sizeof(int)*8);

I know it's equal to sizeof(int). The size of an int is really compiler dependent. Back in the day, when processors were 16 bit, an int was 2 bytes. Nowadays, it's most often 4 bytes on a 32-bit as well as 64-bit systems.

Still, using sizeof(int) is the best way to get the size of an integer for the specific system the program is executed on.

EDIT: Fixed wrong statement that int is 8 bytes on most 64-bit systems. For example, it is 4 bytes on 64-bit GCC.

Ref: https://stackoverflow.com/questions/11438794/is-the-size-of-c-int-2-bytes-or-4-bytes

5. Program to check whether the given number is positive or negative using bitwise operator.

take example of 8 bit number.

An n-bit integer in that format can store numbers between 

between −(2n−1) to (2n−1)-1 and so  in our case, between -128 and 127.

postive number:

1. 127 = 0111 1111
2. 11 = 0000 1011

negative number:

1. -128 = 1000 0000
2. - 11 = 1111 0101

so in the positive number MSB always 0 and in negative number LSB always 1.

// had assumption that  it is 32 bit machine and integer is having size of 32 bits
int sign(int x) {
    return ((x>>31)&1);
}

// better solution independent of compiler is 32 bit or 64 bit
If you can count on your compiler not being crap you should replace 31 with (CHAR_BIT*sizeof(int)-1). Portability and all that.
int sign(int x) {
    return ((x>>( (8*sizeof(int))-1 )&1);
}

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ cat sign.c

#include<stdio.h>

int main()

{

    int a=10,b=-1;

    if ( a >> ((8*sizeof(int))-1)) {

     printf("\n a is negative");

    } else {

     printf("\n a is positive");

    }

    if ( b >> ((8*sizeof(int))-1)) {

     printf("\n b is negative\n");

    } else {

     printf("\n b is positive\n");

    }



    return 0;

}

[tselva@bng-junos-d037 /b/tselva/bcopy/bk_copy_needed/copy-needed/work_tips_dir/sample_c_program]$ ./a.out



 a is positive

 b is negative

Ref: https://www.quora.com/How-are-negative-numbers-stored-in-memory-in-Java

https://www.reddit.com/r/C_Programming/comments/105von/how_to_check_positivezeronegative_using_bitwise/

http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign

6. program to check whether given two numbers having opposite sign

Detect if two integers have opposite signs
int x, y;               // input values to compare signs

bool f = ((x ^ y) < 0); // true iff x and y have opposite signs

if(x^y) { print "both having  opposite sign" } 
else    { print "both having same sign" }

Ref:http://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns

7. intersting facts:

- The left shift and right shift operators should not be used for negative numbers

-The left-shift and right-shift operators are equivalent to multiplication and division by 2 respectively.

- The & operator can be used to quickly check if a number is odd or even

- The ~ operator should be used carefully

// Note that the output of following program is compiler dependent int main() {    unsigned int x = 1;    printf("Signed Result %d \n", ~x);    printf("Unsigned Result %ud \n", ~x);    return 0; } /* Output: Signed Result -2 Unsigned Result 4294967294d */

8.  c program to calculate the two's complement of  integer number:

4 = 0100

then we invert all the bits

0100 -> 1011

finally we add one bit

1011 + 1 = 1100.

x=(~y)+1;

ref: http://www.programminglogic.com/how-computers-represent-negative-binary-numbers/

---> has to see how binary represenation of the number's two complement can be calculated

9. why two's complement of negative number stored in the memory rather than setting MSB bit as 1

-1 is represented by 11111111 (two's complement) rather than (to me more intuitive) 10000001 which is binary 1 with first bit as negative flag.

Say you have two numbers, 2 and -1. In your "intuitive" way of representing numbers, they would be 0010 and 1001, respectively (I'm sticking to 4 bits for size). In the two's complement way, they are 0010 and 1111. Now, let's say I want to add them.

Two's complement addition is very simple. You add numbers normally and any carry bit at the end is discarded. So they're added as follows:

  0010
+ 1111
=10001
= 0001 (discard the carry)

0001 is 1, which is the expected result of "2+(-1)" to be.

But in your "intuitive" method, adding is more complicated:

  0010
+ 1001
= 1011

Which is -3, right? Simple addition doesn't work in this case. You need to note that one of the numbers is negative and use a different algorithm if that's the case

Ref: https://stackoverflow.com/questions/1125304/why-is-twos-complement-used-to-represent-negative-numbers

10. how to find the interger max value

#define MAX_VALUE(a) (((unsigned long long)1 << (sizeof(a) * CHAR_BIT)) - 1)

Definition: INT_MAX = (1 << 31) - 1 for 32-bit integer (2^31 - 1)

When using it, be careful it is assigned to a type large enough. For example:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define IS_TYPE_SIGNED(a) ((a-1) < 0)
#define MAX_VALUE_UNSIGNED(a) (((unsigned long long)1 << \
        (sizeof(a) * CHAR_BIT)) - 1)
#define MAX_VALUE_SIGNED(a) (MAX_VALUE_UNSIGNED(a) >> 1)
#define MAX_VALUE(a) (IS_TYPE_SIGNED(a) ? \
        MAX_VALUE_SIGNED(a) : MAX_VALUE_UNSIGNED(a))

int main(void)
{
    unsigned int i = 0;
    signed int j = 0;

    printf("%llu\n", MAX_VALUE(i));
    printf("%llu\n", MAX_VALUE(j));
    return EXIT_SUCCESS;
}

This prints out:

4294967295
2147483647

Ref: 

https://stackoverflow.com/questions/12762040/get-the-maximum-value-of-a-variable-in-c

https://stackoverflow.com/questions/31897880/how-to-programmatically-determine-integer-max-min-in-c

11. how to swap the two values without temp variable:
  

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int main(void)
{
    int x=3,y=5;
    x=x^y;
    y=x^y;
    x=x^y;
}