StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>How many numbers have 6 consecutive 0 bits (even when considering 2 consecutive bytes)?</p> <pre><code>Byte 1 XXXXXXXX 000000?? 0/1/2/3 ?000000? 0/1/128/129 ??000000 0/64/128/192 </code></pre> <p>So if we consider 1 byte at a time then 0/1/2/3/64/128/192</p> <pre><code>Byte a Byte b XXXXXXXX XXXXXXXX ??100000 0??????? (a & 31 == 0) && (b & 128 == 0) ???10000 00?????? (a & 15 == 0) && (b & 192 == 0) ????1000 000????? (a & 7 == 0) && (b & 224 == 0) ?????100 0000???? (a & 3 == 0) && (b & 240 == 0) ??????10 00000??? (a & 1 == 0) && (b & 248 == 0) </code></pre> <p>So an absolute maximum of 12 tests gives you all combinations.<br> I am sure if you do the comparisons smartly you can reduce that. </p> <p>If we steel @Michael Burr solution below for using a table driven approach. Then we can organize it so that you can do one or two comparisons per byte.</p> <pre><code>struct TestStruct { bool is6Consecutive; bool hasTrailing; int maskNextByte; int offset; }; TestStruct testData[256]; std::size_t findOffsetOf_6ConsecutiveZero(char const* data, size_t size) { for(int loop = 0;loop < (size-1); ++loop) { char const& val = data[loop]; TestStructure const& test = testData[val]; if (test.is6Consecutive) { return loop*8 + test.offset; } if (test.hasTrailing) { if ((data[loop + 1] & test.maskNextByte) == 0) { return loop*8 + test.offset; } } } // Test last byte TestStructure const& test = testData[data[size-1]]; if (test.is6Consecutive) { return (size-1)*8 + test.offset; } return -1; } </code></pre> <p>First few table entries:</p> <pre><code>TestStruct testData[256] = { {true, false, 0x00, 0}, {true, false, 0x00, 0}, {true, false, 0x00, 0}, {true, false, 0x00, 0}, {false, true, 0xf0, 6}, // 4 => 00000100 <Next 4 bytes are zero we hit> {false, false, 0x00, 0}, // 5 => 00000101 <Ignore and move on> {false, true, 0xf8, 7}, // 6 => 00000110 <Next 5 bytes are zero we hit> etc... }; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload