yeah man i am sorry <> means << . and 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
(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 (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: let 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.
PRIYARANJAN: I 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 :)
Implement a function getbits, that returns the(right adjusted) n bits that begin at position p of an integer. Assume bit position 0 is at the right end and that n and p are sensible positive values.
You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
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