Bit stream has an alternating pattern or not

Write a function that returns true if the bit stream has an alternating pattern.
For example 000000101010 would return true and 0000001010000 would return false. Also write test cases for the function.

Strategy:

bool patternCheck(int a)
{
int b=a>>1;
/*if a=000000101010 then b=0=00000010101,,,,rightshift of a by 1*/
//now xor of a and b
int n=(a^b)+1;//n is in 2^n format if alternate bits are there
if(n & (n-1)) == 0) return true;
return false;
}

BIT Manipulation puzzles

Convert number 2 --> 37 without using any other operator but bitwise ? 

Solution:
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
   int x = 2;
    printf("X before :%d\n",x);
    x = (x<<x<<x) |  x<<!!x | !!x ;
    printf("X After  :%d\n",x);
     getchar();
     return(0);
} 

Scan for a bit pattern in a stream of bits

We need to scan for a 16 bit word in a bit stream. It is not guaranteed to be aligned on byte or word boundaries.
There are various brute force methods; using tables and/or shifts.But what is the best way to do this ?

Find parity of an unsigned integer

Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.

Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.

Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0      
      a. Invert parity 
             parity = !parity
      b. Unset rightmost set bit
             n = n & (n-1)
3. return parity

Example:
 Initialize: n = 13 (1101)   parity = 0

n = 13 & 12  = 12 (1100)   parity = 1
n = 12 & 11 = 8  (1000)   parity = 0
n = 8 & 7 = 0  (0000)    parity = 1

Code:

# include <stdio.h> # define  bool int bool getParity(unsigned int n) {     bool parity = 0;     while (n)     {         parity = !parity;         n      = n & (n - 1);     }            return parity; } int main() {     unsigned int n = 7;     printf("Parity of no %d = %s",  n,              (getParity(n)? "odd": "even"));           getchar();     return 0; }

Above solution can be optimized by using lookup table.
Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).
Uses: Parity is used in error detection and cryptography.

Representation of things in memory

How does the computer store things in Memory

You probably know that everything on a computer is stored as strings of bits (binary digits; you can think of them as lots of little on-off switches). Here I'll explain how those bits are used to represent the letters and numbers that your computer is crunching.

Word Size :-
Before we can go into this, you need to understand about the word size of your computer. The word size is the computer's preferred size for moving units of information around; technically it's the width of your processor's registers, which are the holding areas your processor uses to do arithmetic and logical calculations. When people write about computers having bit sizes (calling them, say, "32-bit" or "64-bit" computers), this is what they mean.

The computer views your memory as a sequence of words numbered from zero up to some large value dependent on your memory size. That value is limited by your word size, which is why programs on older machines like 286s had to go through painful contortions to address large amounts of memory.

Numbers

Integer numbers are represented as either words or pairs of words, depending on your processor's word size. One 64-bit machine word is the most common integer representation.
Integer arithmetic is close to but not actually mathematical base-two. The low-order bit is 1, next 2, then 4 and so forth as in pure binary. But signed numbers are represented in twos-complement notation. The highest-order bit is a sign bit which makes the quantity negative, and every negative number can be obtained from the corresponding positive value by inverting all the bits and adding one. This is why integers on a 64-bit machine have the range -2⁶³ to 2⁶³ - 1. That 64th bit is being used for sign; 0 means a positive number or zero, 1 a negative number.
Some computer languages give you access to unsigned arithmetic which is straight base 2 with zero and positive numbers only.
Most processors and some languages can do operations in floating-point numbers (this capability is built into all recent processor chips). Floating-point numbers give you a much wider range of values than integers and let you express fractions. The ways in which this is done vary and are rather too complicated to discuss in detail here, but the general idea is much like so-called ‘scientific notation’, where one might write (say) 1.234 * 10²³; the encoding of the number is split into a mantissa (1.234) and the exponent part (23) for the power-of-ten multiplier (which means the number multiplied out would have 20 zeros on it, 23 minus the three decimal places).

Characters

Characters are normally represented as strings of seven bits each in an encoding called ASCII (American Standard Code for Information Interchange). On modern machines, each of the 128 ASCII characters is the low seven bits of an octet or 8-bit byte; octets are packed into memory words so that (for example) a six-character string only takes up two memory words. For an ASCII code chart, type ‘man 7 ascii’ at your Unix prompt.
The preceding paragraph was misleading in two ways. The minor one is that the term ‘octet’ is formally correct but seldom actually used; most people refer to an octet as byte and expect bytes to be eight bits long. Strictly speaking, the term ‘byte’ is more general; there used to be, for example, 36-bit machines with 9-bit bytes (though there probably never will be again).
The major one is that not all the world uses ASCII. In fact, much of the world can't — ASCII, while fine for American English, lacks many accented and other special characters needed by users of other languages. Even British English has trouble with the lack of a pound-currency sign.
There have been several attempts to fix this problem. All use the extra high bit that ASCII doesn't, making it the low half of a 256-character set. The most widely-used of these is the so-called ‘Latin-1’ character set (more formally called ISO 8859-1). This is the default character set for Linux, older versions of HTML, and X. Microsoft Windows uses a mutant version of Latin-1 that adds a bunch of characters such as right and left double quotes in places proper Latin-1 leaves unassigned for historical reasons.
Latin-1 handles western European languages, including English, French, German, Spanish, Italian, Dutch, Norwegian, Swedish, Danish, and Icelandic. However, this isn't good enough either, and as a result there is a whole series of Latin-2 through -9 character sets to handle things like Greek, Arabic, Hebrew, Esperanto, and Serbo-Croatian.
The ultimate solution is a huge standard called Unicode (and its identical twin ISO/IEC 10646-1:1993). Unicode is identical to Latin-1 in its lowest 256 slots. Above these in 16-bit space it includes Greek, Cyrillic, Armenian, Hebrew, Arabic, Devanagari, Bengali, Gurmukhi, Gujarati, Oriya, Tamil, Telugu, Kannada, Malayalam, Thai, Lao, Georgian, Tibetan, Japanese Kana, the complete set of modern Korean Hangul, and a unified set of Chinese/Japanese/Korean (CJK) ideographs.
Recent versions of Linux use an encoding of Unicode called UTF-8. In UTF, characters 0-127 are ASCII. Characters 128-255 are used only in sequences of 2 through 4 bytes that identify non-ASCII characters.

Interger to Bit String

Write a function to convert an integer into a bit string. For example, if input is 2, the output is "00000000000000000000000000000010" if the system is 32-bit, "0000000000000010" if the system is 16-bit and so on.

Strategy:
We will use bitwise manipulation and convert one bit at a time to character. We look at the right most bit and if it is a 0 bit, we add '0' character into our bit string. Otherwise, we add '1' character into our bit string.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BITS_PER_BYTE 8

char* int2bin(int num)
{
  int bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char)+1;

  char* p = (char*)malloc(bitStrLen);


  for (int i = (bitStrLen-1); i >= 0; i--)
  {
   if(i==bitStrLen-1)
      *(p+i)='\0';
   else
   {
    int k = 1 & num;
    *(p + i) = ((k == 1) ? '1' : '0');
    num >>= 1;}
  }
  return p;
}

int main()
{
  int num=156;
  size_t count=sizeof(int) * BITS_PER_BYTE * sizeof(char);
  char *str=(char*)malloc(count);
 
  memset (str,0,count);
  str=int2bin(num);

 printf(" The string format is %s\n",str);
  getchar();
  return 0;
}

Pending

Next Multiple of 8

To find the next multiple of 8 of a number using only bit-wise manipulations 

Code: 

#include <stdio.h>
#include <stdlib.h>
int nextmul8(int n)
{
    if(n & 7) //if it is not multiple of 8
    {
        n &= ~7; //turn off last 3 bits

        //Add 8 to n
        int m = 8;

        while(n & m)
        {
            n &= ~m;
            m <<= 1;
        }

        n |= m;
    }
    return n;
}

int main()
{
    int n;

    scanf("%d", &n);

    printf("%d\n", nextmul8(n));
    system("pause");
    return 0;
}

Number of set bits till N

You have given a number N. You need to find out total number of set bits from 0 to N.

Example:

Given number is 5. We can represent number 0 to 5 in binary format as below:
000
001
010
011
100
101
Total set bit are 7 (0+1+1+2+1+2)

SET k lower order bits

Write a C program to set k lower order bits in C

Two's Complement

Why is Two's Complement is used to represent negative numbers


Useful Links:
http://stackoverflow.com/questions/1125304/why-is-twos-complement-used-to-represent-negative-numbers

Set subset of bits in X equivalent to ones in Y

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100

Solution:

1. Create a mask with 1s but only 0s between positions i and j. AND the mask with N to clear the bits between i and j to 0s.
2. Create another mask with 0s but only 1s between positions i and j. AND the mask with M to clear the bits outside i and j to 0s.
3. OR N and M.

 Code:

int SetRangeBits(int n, int m, int i, int j) {
    int max = ~0; /* All 1's */

    // 1's through position j, then 0's
    int left = max - ((1 << j) - 1);

    // 1's after position i
    int right = ((1 << i) - 1);

    // 1's with 0s between i and j
    int mask = left | right;

    // Clear i through j, then put m in there
    return (n & mask) | (m << i);
}
 
Alternatively,

1. Create a mask where the only zeroes are in bit positions i to j, which is ~(2^j+1 - 2ⁱ)
2. Result = (mask & X) | (Y << i)

Useful Links :
http://www.careercup.com/question?id=8863294

Binary Addition

Implement a function that performs binary addition. Input to the function is two const strings. The function returns a string that holds the result of addition.
char* binaryadd(const char* a, const char* b) { }
Eg. "1001"+"101"="1110"

Useful Links:
http://www.careercup.com/question?id=10353662

Extract Bits

Given two indices in a byte m and n such that m>=n extract all the bits between m and n in a single instruction.

Method 1
if i is the byte given, we can extract bits between n and m where m>=n with the following single instruction.
[i & [(0xFF << m) ^ (0xFF<< n)]] >> n

how this works:
we create 2 maska (Assuming m=5 and n=2)
11100000 0xFF << m
11111100 0xFF << n
Now we take xor of the above which gives us below mask
00011100 [(0xFF << m) ^ (0xFF<< n)]
Now if the apply the & gate with the given byte i (Assuming its 01010101) it gives us below byte.
00010100 [i & [(0xFF << m) ^ (0xFF<< n)]]
Now we can shift the byte n times to the right to get the extracted byte
00000101

Method 2

If 'x' is an int input and 'm' & 'n' are indices with 0-base as LSB, then the output can be written in one instruction as
y = (x & ((1 << (m-1)) - (1 << (n-1)))) >> n;
Explanation:
1) (1<<(m-1)) returns 2 to the power m
2) (1<<(n-1)) returns 2 to the power (n-1)
3) Difference of above 2 returns the mask with all bits set between m and n (both exclusive)
4) Now AND the above mask with original input 'x' to extract bit values for only the bits between m and n (both excluded)
5) I assumed that the expected result needs to be returned considering the (n)th bit as LSB, and hence the last right shift operation for n times.

Let's take an example:
int m = 7; //1st index
int n = 2; // 2nd index
int x = 173; //input = 10101101
Take out bits from 2nd to 7th index both exclusive i.e.1011 
int y = (x & ((1 << (m-1)) - (1 << (n-1)))) >> (n);
//(1<<(7-1)) - (1<<(2-1)) = 01000000 - 00000010 = 00111100
//x & 00111100 = 10101101 & 00111100 = 00101100 (144 in base 10)
//finally, y = 00101100 >> 2= 00001011 (11 in base 10)

if n==1  then take 0xF and shift the 1's right and take AND
  y=x&(0xF<<(8-(m-n+1))) ;

Useful Links:
http://www.careercup.com/question?id=10537073

Swap Individual Bits

Given an 32-bit integer X, swap the i-th and j-th bit. And also swap a bit range between two numbers

We can swap individual bits using XOR technique.
 swap(int n,int i,int j)
{
if( (n & 1<<i)>>i ^ (n & (1<<j))>>j) ) // if bits i and j are different
{
n^= 1<<i;
n^= 1<<j;
}
return n;
}

Swapping ranges of bits
As an example of swapping ranges of bits suppose we have have b = 00101111 (expressed in binary) and we want to swap the n = 3 consecutive bits starting at i = 1 (the second bit from the right) with the 3 consecutive bits starting at j = 5; the result would be r = 11100011 (binary).

unsigned int i, j; // positions of bit sequences to swap
unsigned int n;    // number of consecutive bits in each sequence
unsigned int b;    // bits to swap reside in b
unsigned int r;    // bit-swapped result goes here

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));

This method of swapping is similar to the general purpose XOR swap
trick, but intended for operating on individual bits.   The variable x 
stores the result of XORing the pairs of bit values we want to swap, 
and then the bits are set to the result of themselves XORed with x.   
Of course, the result is undefined if the sequences overlap.

Useful Links:

http://en.wikipedia.org/wiki/XOR_swap_algorithm 

Modulous by 2^n numbers

Modulous by  numbers of the form 2ⁿ can be done by BITWISE ANDing:---


The modulus operator (%) in various languages is costly operation. Ultimately every operator/operation must result in processor instructions. Some processors won’t have modulus instruction at hardware level, in such case the compilers will insert stubs (predefined functions) to perform modulus. It impacts performance.
There is simple technique to extract remainder when a number is divided by another number (divisor) that is power of 2? A number that is an exact power of 2 will have only one bit set in it’s binary representation. Consider the following powers of 2 and their binary representations
2 – 10
4 – 100
8 – 1000
16  - 10000
Note those zeros in red color, they contribute to remainder in division operation. We can get mask for those zeros by decrementing the divisor by 1.
Generalizing the above pattern, a number that can be written in 2ⁿ form will have only one bit set followed by n zeros on the right side of 1. When a number (N) divided by (2ⁿ), the bit positions corresponding to the above mentioned zeros will contribute to the remainder of division operation. An example can make it clear,

N = 87 (1010111 – binary form)

N%2 = N & (2-1) = 1010111 & 1 = 1 = 1
N%4 = N & (4-1) = 1010111 & 11 = 11 = 3

N%8 = N & (8-1) = 1010111 & 111 = 111 = 7

N%16 = N & (16-1) = 1010111 & 1111 = 111 = 7
N%32 = N & (32-1) = 1010111 & 11111 = 10111 = 23

Modulus operation over exact powers of 2 is simple and faster bitwise ANDing. This is the reason, programmers usually make buffer length as powers of 2.
Note that the technique will work only for divisors that are powers of 2.
An Example:
Implementation of circular queue (ring buffer) using an array. Omitting one position in the circular buffer implementation can make it easy to distinguish between full and empty conditions. When the buffer reaches SIZE-1, it needs to wrap back to initial position. The wrap back operation can be simple AND operation if the buffer size is power of 2. If we use any other size, we would need to use modulus operation.

BITWISE operators

Discuss the bitwise operators and how we can use them in real life examples

Useful Links:-
http://www.cprogramming.com/tutorial/bitwise_operators.html
http://snook.ca/archives/javascript/creative-use-bitwise-operators
http://en.wikipedia.org/wiki/Bitwise_operation

Practice Questions regarding BITWISE:
http://graphics.stanford.edu/~seander/bithacks.html
http://www.careercup.com/page?pid=bit-manipulation-interview-questions
http://www.geeksforgeeks.org/archives/category/bit-magic
http://stackoverflow.com/questions/tagged/bit-manipulation

Number of BITS to be flipped to convert A to B

You are given two numbers A and B. Write a program to count number of bits needed to be flipped to convert A to B.

Bit Palindrome

Write a function to check if the bit-wise representation of an integer is a palindrome.
eg. 5, 9, etc. are palindromes.

Toggle / Isolate Bits of anumber

1.Toggle kth bit
2.Toggle rightmost one bit
3.Isolate rightmost 1 bit
4.Isolate rightmost zero bit