swap bits
swap bits in position i and j for a number....in the most efficient way....
[AMAZON] Vertical sum of nodes
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples: 1 / \ 2 3 / \ / \ 4 5 6 7 The tree has 5 vertical lines Vertical-Line-1 has only one node 4 => vertical sum is 4 Vertical-Line-2: has only one node 2=> vertical sum is 2 Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12 Vertical-Line-4: has only one node 3 => vertical sum is 3 Vertical-Line-5: has only one node 7 => vertical sum is 7 So expected output is 4, 2, 12, 3 and 7
int swap(int n)
ReplyDelete{
if (( (n&(1<>i)^((n&(1<>j){
n^=(1<<i);
n^=(1<<j);
}
return n
}
if bits at position i and j are different then flip them.
i wud like to know if u hv mistaken << by <> in 'if condition' or does it hv a special meaning.
ReplyDeleteIn the former case, check ur code if the bits at position i and j are both 1.
we can rather use the condition as:
((n>>i)&1)^((n>>j)&1).
yeah man i am sorry <> means << .
ReplyDeleteand if bits at position i and j are both 1 then they don't need to be swapped.By doing so you are making your program more efficient.
ya i do understand what u want to do but when both the bits are 1...condition turns out to be true because
ReplyDelete(n&(1<<i)) and (n&(1<<j)) will give two different values.
so xoring them will lead to true value.
now inside the loop you are flipping the bits which makes both the 1's 0, which shouldn't happen.
when ith bit and jth bit are both 1 then
ReplyDelete(n&(1<<i) will set all but ith to 0 and ith to 1.
(n&(1<<j) will set all but jth to 0 and jth to 1.
now on xoring them will always give 0.so condition becomes false.
similar will be case with both bit set to 0.
ok take an example:
ReplyDeletelet the no. be 9
its binary representation is 1001.
suppose i=0 and j=3;
consider (n&(1<<i))
(1001&(0001<<0))=(1001&0001)=0001
now consider (n&(1<<j))
(1001&(0001<<3))=(1001&1000)=1000
if you xor the above two
0001^1000=1001=some positive value in decimal.
your condition is satisfied and you know you are flipping the bits inside, so both the bits would become 0 and binary representation of your new no. wud be 0000.
i guess this was not intended.
though your code works perfectly all right in case of both the bits being 0.
we can rather use the condition as:
ReplyDelete((n>>i)&1)^((n>>j)&1).
PRIYARANJAN:
ReplyDeleteI think there is no need for an if statement:
a = (n & (1 << i)) >> i;
b = (n & (1 << j)) >> j;
n ^= (a ^ b) << j;
n ^= (a ^ b) << i;
by the way, nice blog! keep posting :)
@above that if statement is used to avoid one comparison when bits at position i and j are same.
ReplyDelete