swap bits
swap bits in position i and j for a number....in the most efficient way....
Given an integer n, write a function that returns count of trailing zeroes in n!. Examples: Input: n = 5 Output: 1 Factorial of 5 is 20 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
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