Author |
Topic: count total number of bit flips (Read 2775 times) |
|
sambha
Newbie
Posts: 8
|
 |
count total number of bit flips
« on: Feb 28th, 2006, 1:06am » |
 Quote  Modify
|
Problem Statement
You work for a company that sells mechanical bit counting devices. These devices wear out when they do a lot of counting. You are going to see how much wear has been put on one particular 15-bit binary counter. One unit of wear occurs for every bit that is flipped in the counter. For example:
If the counter was at 7 = 000000000000111
And it was incremented to 8 = 000000000001000
Then 4 bits are flipped so 4 units of wear would occur. If a counter was incremented through an inclusive range like 7 -> 12 then :
Starts at 7 = 000000000000111
Goes to 8 = 000000000001000 7 -> 8 = 4 units of wear
Goes to 9 = 000000000001001 8 -> 9 = 1 unit of wear
Goes to 10 = 000000000001010 9 -> 10 = 2 units of wear
Goes to 11 = 000000000001011 10 -> 11 = 1 unit of wear
Goes to 12 = 000000000001100 11 -> 12 = 3 units of wear
This causes a total of 4+1+2+1+3 = 11 units of wear. Return the total wear caused by incrementing the counter through the inclusive range between start and finish.
Definition
Class:
MechanicalCounter
Method:
amountWear
Parameters:
int, int
Returns:
int
Method signature:
int amountWear(int start, int finish)
(be sure your method is public)
Constraints
-
start will be less than finish.
-
start will be between 0 and 32766 inclusive.
-
finish will be between 1 and 32767 inclusive.
Examples
0)
7
8
Returns: 4
As seen above, 4 units of wear occur when 7 becomes 8.
1)
7
12
Returns: 11
The example in the problem statement.
2)
1
32767
Returns: 65518
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: count total number of bit flips
« Reply #1 on: Feb 28th, 2006, 2:14am » |
Quote Modify
|
This looks very much copied from somewhere.. homework?
In any case, one hint is that the wear between x and y is equal to the wear between 0 and y minus the wear between 0 and x.
Which is easier to calculate. In the order of the number of bits of the numbers.
Practically you'd expect each bit to withstand equally much wear, so the least significant bit would generally give out long before the others.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: count total number of bit flips
« Reply #2 on: Feb 28th, 2006, 2:59pm » |
Quote Modify
|
The way it is written, it looks like a topCoder assignment.
|
|
IP Logged |
|
|
|
wangwang
Newbie
Posts: 3
|
|
Re: count total number of bit flips
« Reply #3 on: Feb 28th, 2006, 8:46pm » |
Quote Modify
|
write the start number and end number as binary, for example:
start: 0010
end: 1101
let's start from the left-most bit:
obviously, only 1 flip needed for that bit
for the next bit, we need 2*1 + (1-0) flips which is 3
for the third bit, we need 2*3 + (0-1) flps which is 5
for the rightmost bit, we need 2*5 + (1-0) which is 11
so the total will be 20
the point here is that to flip the next higher bit m times, we need fip the bit 2*m + (end_bit - start_bit)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: count total number of bit flips
« Reply #4 on: Mar 1st, 2006, 1:12am » |
Quote Modify
|
int amountWear(int a, int b)
{
return (a==b) ? 0 : ((b-a) + amountWear(a>>1, b>>1));
}
or (less zen but much better runtime);
int amountWear(int a, int b)
{
int c = 0;
while( a!=b ){
c += (b-a);
a >>= 1;
b >>= 1;
}
return c;
}
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: count total number of bit flips
« Reply #5 on: Mar 1st, 2006, 10:15am » |
Quote Modify
|
The magic expression here is (n<<1)--.
|
|
IP Logged |
|
|
|
souvenir
Newbie
Posts: 1
|
|
Re: count total number of bit flips
« Reply #6 on: Mar 9th, 2006, 5:30pm » |
Quote Modify
|
for number n, the number of flips from 0 to n is
2*n - (number of 1's in the binary format of n)
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: count total number of bit flips
« Reply #7 on: Mar 19th, 2006, 5:34am » |
Quote Modify
|
I'd do it a bit like...
count = 0;
for ( i = start; i < end; i++ )
{
fliparray = i XOR (i+1)
count = count + bitcount(fliparray);
}
Probably not really efficient, might be improved, true, and dependend on the efficiency of bitcount.
One way to improve efficiency:
int count = 0;
int j;
for ( i = j = start; i <= end; j = i++ )
{
count += bitcount(i XOR j);
}
prevents calculating i+1 all the time  Needs more storage, but anyhow...
I hope it kinda works
|
|
IP Logged |
|
|
|
cwolves
Newbie
Posts: 41
|
|
Re: count total number of bit flips
« Reply #8 on: Apr 7th, 2006, 8:23pm » |
Quote Modify
|
this is rediculously easy...
For each number you have one swap for each bit number every time a number "passes over" a power of two...so just add the possible powers of 2 for 0-->16.
javascript implementation:
Code:function countSwaps(n){
for(var i=0, m=0; i<16; i++)
m+=Math.floor(n/Math.pow(2, i));
return m;
}
function totalSwaps(a, b){ return countSwaps(b)-countSwaps(a); }
alert(totalSwaps(1, 32767)); |
|
|
|
IP Logged |
|
|
|
acumen
Newbie
 
Posts: 13
|
|
Re: count total number of bit flips
« Reply #9 on: May 19th, 2006, 10:37am » |
Quote Modify
|
Hi Grimbal,
Can you explain me how did you come to the following stand?
int amountWear(int a, int b)
{
return (a==b) ? 0 : ((b-a) + amountWear(a>>1, b>>1));
}
please explain me how does this work
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: count total number of bit flips
« Reply #10 on: May 22nd, 2006, 12:45am » |
Quote Modify
|
It is quite simple.
The last bit flips for every increment. That is (b-a) flips. I can then ignore the last bit. To do so, I drop the last bit with a shift (>>1) and count the flips in the remaining bits by calling the same procedure recursively.
so:
- "(a==b) ? 0 : " tells that if a and b are the same, the result is zero. It helps to exit the recursion.
- "(b-a)" counts the flips on the last bit
- "amountWear(a>>1, b>>1)" counts the flips on all the previous bits.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print