Binary question

  • Thread starter Thread starter William Stacey
  • Start date Start date
W

William Stacey

Given any arbitrary byte (or int for that matter), is there a way to figure
out:
1) The *number of one's set without a loop? Maybe some formula?.
2) Looking from left the right, if all 1's are continuous with not
intervening 0's. 0's on the end ok.

TIA
 
William Stacey said:
Given any arbitrary byte (or int for that matter), is there a way to figure
out:
1) The *number of one's set without a loop? Maybe some formula?.
2) Looking from left the right, if all 1's are continuous with not
intervening 0's. 0's on the end ok.
Click to expand...

I would use an array that is filled with the required information at compile
time, and the byte as index to the array at run-time.

Jens.
 
Yes I could do that and thanks for the reply. I was just thinking this
could be done with math.
 
FYI. Did some more testings and research and came up with this. Any
optimizations?

/// <summary>
/// Returns the number of "1" bits set in any uint.
/// </summary>
public static int BitCount(uint x)
{
int bitCount = 0;

if ( x != 0)
{
do
{
bitCount++;
x = x & (x - 1);
} while (x != 0);
}
return bitCount;
}

/// <summary>
/// Given any uint, returns true if the 1 bits are contiguous from left to
right.
/// This method will also return to the "out" parameter the number of 1 bits
in
/// the num, even if the bits are not contiguous.
/// </summary>
public static bool ContiguousBits(uint num, out int bitCount)
{
int shift = 0;
int bc = 0;

bc = Bits.BitCount(num); //The BitCount Method above.
shift = 32 - bc;
bitCount = bc;
return ( (num >> shift) == (Math.Pow(2, bc) - 1) );
}
 
Your question was - 'without using a loop'....

The fastest algorithm, if using Assembly, would be to use one register and
loop a right shift operation and add the flag bit everytime.

However, the fastest, if holding an array of lookup is not a problem, would
be to construct a 256 lookup table upfront and take 8bits at a time and look
up 4 times for a 32 bit number.

vJ
 
Given any arbitrary byte (or int for that matter), is there a way to figure
out:
1) The *number of one's set without a loop? Maybe some formula?.
2) Looking from left the right, if all 1's are continuous with not
intervening 0's. 0's on the end ok.

TIA
Click to expand...

For (1) above you could use...

int bitcount(int i)
{
i = (i & 0x55555555) + ((i>>1) & 0x55555555);
i = (i & 0x33333333) + ((i>>2) & 0x33333333);
i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);
return (i % 255);
}

Oz
 
William Stacey said:
do
{
bitCount++;
x = x & (x - 1);
} while (x != 0);
Click to expand...

looks very nice! Someone told me once that the NSA requested Cray to
implement BitCount() in hardware in the early days, and that all their
machines had this unit.
public static bool ContiguousBits(uint num, out int bitCount)
{
int shift = 0;
int bc = 0;

bc = Bits.BitCount(num); //The BitCount Method above.
shift = 32 - bc;
bitCount = bc;
return ( (num >> shift) == (Math.Pow(2, bc) - 1) );
}
Click to expand...

Wouldn't it be sufficient to test

0 == (0xFFFFFFFF>>bc) & num

once you have the bit count?

x86 assembly has BSF/BSR which you could exploit...

Jens.
 
BTW - any chance you have a few lines that will set a range of bits to a
supplied bit mask. Maybe with a sig like:
int SetBits(uint src, int pos, int count, uint bitMask)
{
...
return x; //Returns the new uint with the bitMask (1's and/or 0's)
applied to the pos with max count bits.
}
TIA again :-)
 
Hi William,

Based on my understanding, you want to get part of bitMask's(From right to
left: [pos, pos+count]) and apply it & with num.
So you can do like this:
int SetBits(uint src, int pos, int count, uint bitMask)
{
uint centerMask=((0xFFFFFFFF<<(32-count))>>(32-pos-count));
x=((centerMask&bitMask)&src);
return x;
}

If I misunderstand you, please feel free to tell me.

Best regards,
Jeffrey Tan
Microsoft Online Partner Support
Get Secure! - www.microsoft.com/security
This posting is provided "as is" with no warranties and confers no rights.
 
Back
Top