Unknown - Jul 6, 2014
intPart »= 1; this is fr wat?
Hi Chaitrali, sorry for the delayed response. This means division by 2.
In general, bit_arg»shift_arg shifts bits to of bit_arg shift_arg places to the right – equivalent to integer division by 2^shift_arg
Problem
Given a sorted integer array and number z find all pairs (x, y) in the array so that x + y < z. Can it be done better than O(n^2)?
Solution
Method 1
The solution can be found in O(n^2) where we select 1st element from n elements and 2nd element y from n-1 elements, and hence n(n-1)/2 ~ O(n^2)
Reference - stackoverflow
Problem
Divide a number by 3 without using *, /, +, -, % operators
Solution
Method 1 - Divide the number using bitwise operator
We have already discussed how to divide a number by 3 with the help of ‘+’ operator here. So, all we have to do is write a plus operator with the help of bitwise operator, which we have done here.
// replaces the + operator
int add(int x, int y) {
int a, b;
do {
a = x & y;
b = x ^ y;
x = a << 1;
y = b;
} while (a);
return b;
}
int divideby3 (int num) {
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}