Algorithm Bit

逐位比较bit
https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/bit.html
Single Number II
在一个数组里，有一个数出现了一次，别的数都出现了恰好三次，找那个single number。对于每一位bit，统计所有number在这一位上是0或1，如果是1的总数余3不为0，那那个single number在这个bit位上是1

    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                result |= 1 << i;
            }
        }
        return result;
    }

Majority Element
对于每一位bit，统计所有number在这位上出现1的次数。如果次数*2大于array的length，那majority element在这位上是1。

    public int majorityElement(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            if (count * 2 > nums.length) {
                result |= 1 << i;
            }
        }
        return result;
    }

    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int n1 = x >> i & 1;
            int n2 = y >> i & 1;
            if (n1 != n2) {
                count++;
            }
        }
        return count;
    }

Power of Four
排除首位，有且只有一位是1的，而且是1的一位的index是偶数的，就是power of four。

    public boolean isPowerOfFour(int num) {
        if (num <= 0) {
            return false;
        }

        int count = 0, index = -1;
        for (int i = 0; i < 32; i++) {
            if ((num >> i & 1) == 1) {
                index = i;
                count++;
            }
        }
        return count == 1 && index % 2 == 0;
    }

    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        } 

        int count = 0;
        for (int i = 0; i < 31; i++) {
            if ((n >> i & 1) == 1) {
                count++;
            }
        }
        return count == 1;
    }

用bit来存储信息
https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/storer-information-by-bit.html


http://www.geeksforgeeks.org/count-minimum-bits-flip-xor-b-equal-c/

Given a sequence of three binary sequences A, B and C of N bits. Count the minimum bits required to flip in A and B such that XOR of A and B is equal to C. 

If we generalize, we will find that at any position of A and B, we just only need to flip ith (0 to N-1) position of either A or B otherwise we will not able to achieve minimum no of Bits.
So at any position of i (0 to N-1) you will encounter two type of situation i.e., either A[i] == B[i] or A[i] != B[i]. Let’s discuss it one by one.

• If A[i] == B[i] then XOR of these bits will be 0, two cases arise in C[]: C[i]==0 or C[i]==1.
  If C[i] == 0, then no need to flip the bit but if C[i] == 1 then we have to flip the bit either in A[i] or B[i] so that 1^0 == 1 or 0^1 == 1.
• If A[i] != B[i] then XOR of these Bits gives a 1, In C two cases again arise i.e., either C[i] == 0 or C[i] == 1.
  Therefore if C[i] == 1, then we need not to flip the bit but if C[i] == 0, then we need to flip the bit either in A[i] or B[i] so that 0^0==0 or 1^1==0

int totalFlips(char *A, char *B, char *C, int N)

{

    int count = 0;

    for (int i=0; i < N; ++i)

    {

        // If both A[i] and B[i] are equal

        if (A[i] == B[i] && C[i] == '1')

            ++count;

        // If Both A and B are unequal

        else if (A[i] != B[i] && C[i] == '0')

            ++count;

    }

    return count;

}

http://www.geeksforgeeks.org/count-trailing-zero-bits-using-lookup-table/

Given an integer, count the number of trailing zeroes. For example, for n = 12, its binary representation is 1100 and number of trailing zero bits is 2.

The lookup table solution is based on following concepts :

1. The solution assumes that negative numbers are stored in 2’s complement form which is true for most of the devices. If numbers are represented in 2’s complement form, then (x & -x) [Bitwise and of x and minus x] produces a number with only last set bit.
2. Once we get a number with only one bit set, we can find its position using lookup table. It makes use of the fact that the first 32 bit position values are relatively prime with 37, so performing a modulus division with 37 gives a unique number from 0 to 36 for each. These numbers may then be mapped to the number of zeros using a small lookup table.

int countTrailingZero(int x)

{

     // Map a bit value mod 37 to its position

     static const int lookup[] = {32, 0, 1,

     26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11,

     0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29,

     10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19,

     18};

     // Only difference between (x and -x) is

     // the value of signed magnitude(leftmostbit)

     // negative numbers signed bit is 1

     return lookup[(-x & x) % 37];

}

int countTrailingZero(int x)

{

  int count = 0;

  while ((x & 1) == 0)

  {

      x = x >> 1;

      count++;

  }

  return count;

}

http://www.geeksforgeeks.org/find-sum-sum-sub-sequences/

Given an array of n integers. The task is to find the sum of sum of each of sub-sequence of the array.

Method 1 (brute force):
Generate all the sub-sequence and find the sum of each sub-sequence.

Method 2 (efficient approach):
For an array of size n, we have 2^n sub-sequences (including empty) in total. Observe, in total 2nsub-sequences, each elements occurs 2n-1 times.

So, sum of sum of all sub-sequence will be (sum of all the elements) * 2n-1.

int sum(int arr[], int n)

{

  int ans = 0;

  // Finding sum of the array.

  for (int i = 0; i < n; i++)

    ans += arr[i];

  return ans * pow(2, n - 1);

}

http://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

http://www.geeksforgeeks.org/sum-xor-possible-subsets/

Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all the elements of the subsets.

A Naive approach is to take the XOR all possible combination of array[] elements and then perform the summation of all values. Time complexity of this approach grows exponentially so it would not be better for large value of n.

An Efficient approach is to find the pattern with respect to the property of XOR. Now again consider the subset in binary form like:

    1 = 001
    5 = 101
    6 = 110
1 ^ 5 = 100
1 ^ 6 = 111
5 ^ 6 = 011
1^5^6 = 010

So if we analyze all these binary number of the XORs, we can observe that set bit occurs at all the position of i(0 to n-1) will exactly contribute to half of 2n. So we can easily imposed these two condition at each such positions of i.

• If there is any value of arr[] that has set tth bit set, then exactly half of 2n subsets will be of the form, so they will contribute to 2n-1+i to the final sum.
• If there is no value of arr[] that ith bit set, then we can say that there will be no term in all subsets that have a ith bit set.

Now the question boils down to check which position of element of the arr[] will be set or not. But here is some trick that we will not iterate for all elements one by one in spite of that we can simple take the OR of all such values and multiply with 2n-1, For example:-

Take a OR of all arr[] elements, we get 
= 1 | 5 | 6
= 001 | 101 | 110
= 111

Now to find final summation, we can write it down as:-
= 1*2n-1+2 + 1*2n-1+1 + 1*2n-1+0
= 2n-1 * (1*22 + 1*21 + 1*20 )
= 2n-1 * (1112)
= 2n-1 * 7

Put n = 3,  we get
= 28

So at last for any value of n and array elements, we can simple say that the final sum will be 2n-1times the bitwise OR of all the inputs.

int xorSum(int arr[], int n)

{

    int bits = 0;

    // Finding bitwise OR of all elements

    for (int i=0; i < n; ++i)

        bits |= arr[i];

    int ans = bits * pow(2, n-1);

    return ans;

}

http://www.geeksforgeeks.org/given-a-set-find-xor-of-the-xors-of-all-subsets/

The question is to find XOR of the XOR’s of all subsets. i.e if the set is {1,2,3}. All subsets are : [{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]. Find the XOR of each of the subset and then find the XOR of every subset result.

This is a very simple question to solve if we get the first step (and only step) right. The solution is XOR is always 0 when n > 1 and Set[0] when n is 1.

int findXOR(int Set[], int n)

{

    // XOR is 1 only when n is 1, else 0

    if (n == 1)

       return Set[0];

    else

       return 0;

}

The logic goes simple. Let us consider n’th element, it can be included in all subsets of remaining (n-1) elements. The number of subsets for (n-1) elements is equal to 2(n-1) which is always even when n>1. Thus, in the XOR result, every element is included even number of times and XOR of even occurrences of any number is 0.

http://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/

For any given two numbers n and m, you have to find n*m without using any multiplication operator.

We can solve this problem with the shift operator. The idea is based on the fact that every number can be represented in binary form. And multiplication with a number is equivalent to multiplication with powers of 2. Powers of 2 can be obtained using left shift operator.

Check for every set bit in the binary representation of m and for every set bit left shift n, count times where count if place value of the set bit of m and add that value to answer.

int multiply(int n, int m)

{ 

    int ans = 0, count = 0;

    while (m)

    {

        // check for set bit and left

        // shift n, count times

        if (m % 2 == 1)             

            ans += n << count;

        // increment of place value (count)

        count++;

        m /= 2;

    }

    return ans;

}

http://www.geeksforgeeks.org/check-divisibility-binary-stream/

Stream of binary number is coming, the task is to tell the number formed so far is divisible by a given number n.
At any given time, you will get 0 or 1 and tell whether the number formed with these bits is divisible by n or not.

Actually that question was a bit simple, interviewer fixed the n to 3.

Method 2 (Doesn’t cause overflow) :
In this solution, we just maintain the remainder if remainder is 0, the formed number is divisible by n otherwise not. This is the same technique that is used in Automata to remember the state. Here also we are remembering the state of divisibility of input number.

In order to implement this technique, we need to observe how the value of a binary number changes, when it is appended by 0 or 1.

Let’s take an example. Suppose you have binary number 1.
If it is appended by 0 it will become 10 (2 in decimal) means 2 times of the previous value.
If it is appended by 1 it will become 11(3 in decimal), 2 times of previous value +1.

How does it help in getting the remainder?
Any number (n) can be written in the form m = an + r where a, n and r are integers and r is the remainder. So when m is multiplied by any number so the remainder. Suppose m is multiplied by x so m will be mx = xan + xr. so (mx)%n = (xan)%n + (xr)%n = 0 + (xr)%n = (xr)%n;

We need to just do the above calculation (calculation of value of number when it is appended by 0 or 1 ) only over remainder.

When a binary number is appended by 0 (means 
multiplied by 2), the new remainder can be 
calculated based on current remainder only.
r = 2*r % n;

And when a binary number is appended by 1.
r = (2*r + 1) % n; 

    while (true)

    {

        // Read next incoming bit via standard

        // input. 0, 00, 000.. are same as int 0

        // ans 1, 01, 001, 00..001 is same as 1.

        int incomingBit;

        cin >> incomingBit;

        // Update remainder

        if (incomingBit == 1)

            remainder = (remainder * 2 + 1) % n;

        else if (incomingBit == 0)

            remainder = (remainder * 2) % n;

        else

            break;

        // If remainder is 0.

        if (remainder % n == 0)

            cout << "yes \n";

        else

            cout << "no \n";

    }

http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/