wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> count total number of bit flips
        
(Message started by: sambha on Feb 28^th, 2006, 1:06am)

Title: count total number of bit flips
Post by sambha on Feb 28^th, 2006, 1:06am

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

Title: Re: count total number of bit flips
Post by towr on Feb 28^th, 2006, 2:14am

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.

Title: Re: count total number of bit flips
Post by Grimbal on Feb 28^th, 2006, 2:59pm

The way it is written, it looks like a topCoder assignment.

Title: Re: count total number of bit flips
Post by wangwang on Feb 28^th, 2006, 8:46pm

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)

Title: Re: count total number of bit flips
Post by Grimbal on Mar 1^st, 2006, 1:12am

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;
}

Title: Re: count total number of bit flips
Post by KWillets on Mar 1^st, 2006, 10:15am

The magic expression here is [hide](n<<1)--[/hide].

Title: Re: count total number of bit flips
Post by souvenir on Mar 9^th, 2006, 5:30pm

for number n, the number of flips from 0 to n is
2*n - (number of 1's in the binary format of n)

Title: Re: count total number of bit flips
Post by Sjoerd Job Postmus on Mar 19^th, 2006, 5:34am

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

Title: Re: count total number of bit flips
Post by cwolves on Apr 7^th, 2006, 8:23pm

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));

Title: Re: count total number of bit flips
Post by acumen on May 19^th, 2006, 10:37am

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

Title: Re: count total number of bit flips
Post by Grimbal on May 22^nd, 2006, 12:45am

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.