To tackle the problem systematically, you might employ a
state machine.
E.g. you start by initializing the
max_len
and
gap_len
to
0
, the
State to
Init
and then process one bit after the other by following the states and actions as shown in this table:
Current State | Current Bit | Next State | Action |
---|
Init | 0 | Init | ; |
1 | Count | ; |
Count | 0 | Count | gap_len++; |
1 | Count | max_len = max(max_len, gap_len);
gap_len = 0; |
Finally you return the resulting
max_len
value.
This is functional correct but maybe not optimal. E.g.
max_len
is updated even
gap_len
is zero, etc. But this is only relevant if speed is relevant. In such a case, more states might improve speed for the cost of complexity of the state machine. This is left as exercise, though. ;-)
Now, the state machine translates into something like this:
[EDIT] changed from define to enum [/EDIT]
...
enum { Init, Count } state = Init;
...
int n = ...
int max_len = 0;
int gap_len = 0;
for(int bit = 1; bit; bit<<=1) { int one = n & bit;
switch(state) {
case Init:
if (one) {
state = Count;
}
break;
case Count:
if (one) {
if (max_len < gap_len) max_len = gap_len;
gap_len = 0;
} else {
gap_len++;
}
break;
default:
assert(!"Unexpected State");
break;
}
}
Cheers
Andi