Algorithm to find the most significant bit
This is one approach (not necessarily the most efficient, though, especially if your platform has a single-instruction solution to find-first-one or count-leading-zeros or something similar), assuming twos complement signed integers and a 32-bit integer width.
int mask = (int)(1U<<31); // signed integer with only bit 32 set
while (! n & mask) // n is the int we're testing against
mask >>= 1; // take advantage of sign fill on right shift of negative number
mask = mask ^ (mask << 1) // isolate first bit that matched with n
If you want the bit position of that first one, simply add a integer counter that starts at 31 and gets decremented on each loop iteration.
One downside to this is if n == 0
, it's an infinite loop, so test for zero beforehand.
You could also use bit shifting. Pseudo-code:
number = gets
bitpos = 0
while number != 0
bitpos++ # increment the bit position
number = number >> 1 # shift the whole thing to the right once
end
puts bitpos
if the number is zero, bitpos is zero.
Finding the most significant bit in a word (i.e. calculating log2 with rounding down) by using only C-like language instructions can be done by using a rather well-known method based on De Bruijn sequences. For example, for a 32-bit value
unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
static const unsigned MUL_DE_BRUIJN_BIT[] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27];
}
However, in practice more simple methods (like unrolled binary search) usually work just as well or better.
The edited question is really quite different, though not very clear. Who are "you"? The website or the programmer of the program that reads data from the website? If you're the website, you make the program stop by sending a value (but what, a byte, probably?) with its most-significant bit set. Just OR or ADD that bit in. If you're the programmer, you test the most-significant bit of the values you receive, and stop reading when it becomes set. For unsigned bytes, you could do the test like
bool stop = received_byte >= 128;
or
bool stop = received_byte & 128;
For signed bytes, you could use
bool stop = received_byte < 0;
or
bool stop = received_byte & 128;
If you're not reading bytes but, say, 32bit words, the 128 changes to (1 << 31)
.