Power of 2 or not ?

How to find a number is power of 2 or not ?

bool IsPowerOfTwo(unsigned long x)
{
    return (x != 0) && (x & (x - 1)) == 0);
}

Explanation:

The above function returns bool (true/false) and accepts one incoming parameter of type unsigned long (x, in this case). Lets take an example, that someone has passed value 4 to the function like:

bool b = IsPowerOfTwo(4);

Now replace each occurance of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0); 


We already know (4 != 0) , so the evaluation of the expression is true.


((4 & (4-1)) == 0)  translates to:


((4 & (3)) == 0) 


But what exactly is  4&3 ? The binary representation of 4 is 100 and of 3 is 011. The & operation says that if both values are equal to 1, then the result is 1. Otherwise it is 0.

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

const

What is the difference between char const * and char * const ?

According to the standard, const modifies the element directly to its left. The use of
 const  at the beginning of a declaration is just a convenient mental shortcut. So the following two statements are equivalent:

char const * pointerToConstantContent;
const char * pointerToConstantContent;

In order to ensure the pointer itself is not modifiable,  const  should be placed after the asterisk:

char * const constantPointerToMutableContent;

To protect both the pointer and the content to which it points, we should use two consts as below:

char const * const constantPointerToConstantContent;

Search in a Circular Sorted Array

Given a circular sorted array say A = { 2,3,4,5,6,7,8,9,0,1 }, find a number in it.

If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

Approach:

Find the middle value of the input array a.

If a[0] < a[mid], then all values in the first half of the array are sorted.

If a[mid] < a[last], then all values in the second half of the array are sorted.

Take the sorted half, and check whether your value lies within it (key lies between the sorted half).

• If so, binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process

 
#include <iostream>
#include <vector>
#include <assert.h>

template<typename T, typename type>
int binary_search(const T& a, int left, 
                  int right, type key) {

    while (left <= right) {
        int mid = (right-left)/2 + left;

        // base case 1
        if (a[mid] == key)
            return mid;

        // mid less than key. Move to right
        if (a[mid] < key) {
            left = mid+1;
        }
        else {
            right = mid-1;
        }
    }

    return -1;
}

template<typename T, typename type>
int circular_search(const T& a, int left, 
                    int right, type key) {

    // base case 1
    int mid = (right-left)/2 + left;
    if (a[mid] == key)
        return mid;

    // left array is sorted.
    if (a[0] < a[mid]) {

        if (key > a[left] && key < a[mid]) {
            return binary_search(a, left, mid-1, key);
        }
        else {
            return circular_search(a, mid+1, right, key);
        }
    }
    // right array is sorted
    else if (a[mid] < a[right]) {
        if (key > a[mid] && key < a[right])
            return binary_search(a, mid+1, right, key);
        else
            return circular_search(a, left, mid-1, key);

    }

    return -1;

}

template<typename T>
void print(const T&a) {
    typedef typename T::const_iterator iterator;
    iterator start = a.begin();
    iterator end = a.end();
    for(; start!=end; ++start)
        std::cout << *start << " ";
    std::cout << std::endl;
}

int main() {
    typedef std::vector<int> Input;
    Input temp;
    int n =0;
    
    // get n from user
    std::cin >> n;

    for(int i=0; i<n; ++i) {
        temp.push_back(i*2);
    }
    Input data;
    data.resize(temp.size());

    // Rotate the input sequence
    std::rotate_copy(temp.begin(), temp.begin()+4, 
                     data1.end(), data.begin());
    print(data);

    // get key from user
    int key=0;
    std::cin >> key;

    int found = circular_search<Input, int>(data, 0, n-1, key);
    if (found)
    {
        assert(key == data[found]);
        std::cout << data[found] 
                  << " found @ pos " 
                  << found << std::endl;
    }
    else
        std::cout << key 
                  << " not found" 
                  << std::endl;

    return 0;

}

Hamming sequence

Hamming's Problem

Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2ⁱ3^j5^k for i,j,k at least 0. This list is called the Hamming sequence. The list begins like this:
1 2 3 4 5 6 8 9 10 12 15 16 18 ...

Brute force technique:

Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:

• Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
• Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
• Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.

This obvious technique has one problem: it's unbelievably slow. The problem is that most numbers aren't on the list, and you waste an immense amount of time discovering that. Although the numbers at the beginning of the list are pretty close together, the 2,999th number in the list is 278,628,139,008. Even if you had enough time to wait for the brute-force algorithm to check all the numbers up to 278,628,139,008, think how much longer you'd have to wait for it to finally find the 3,000 number in the sequence, which is 278,942,752,080.

Linear Solution:

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that:
1) a[j]*2 > a[i - 1] and
2) j is smallest possible.

Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)

 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
  // get n from user
  unsigned n;
  cout <<"n: ";
  cin >>n;

  // list of ugly numbers
  vector <uint64_t> ugly;
  uint64_t x = 1;
  ugly.push_back(x);

  // index of next multiple
  unsigned i2 = 0, i3 = 0, i5 = 0;

  // value of next multiple
  uint64_t x2 = 2, x3 = 3, x5 = 5;

  // loop through ugly numbers
  for(unsigned a = 1; a < n; a++) {

    x = std::min(x2, std::min(x3,x5));

    ugly.push_back(x);
    if (x == x2) { i2++; x2 = ugly[i2] * 2; }
    if (x == x3) { i3++; x3 = ugly[i3] * 3; }
    if (x == x5) { i5++; x5 = ugly[i5] * 5; }
  }

  // return last ugly number found
  cout << x << endl;
  return 0;

}