CODEWITHSUNDEEP
algorithmbitbitstring
EricP
EricP

Reputation: 41

Finding two consecutive 1's in a bitstring in less then n time?

I am trying to figure out a way to see if a bitstring has 2 consecutive ones in the bitstring size n in less then n time.

For example, lets say we had a bitstring size 5 (index 0-4). If index 1 and 3 were both 0's, I could return false. But if they were both ones then I may have to do 5 peeks to find my answer.

The bitstring doesn't have to be length 5. For simplicity's sake, lets say it can be between 3 and 8.

Upvotes: 4

Views: 2043

Answers (1)

Paul R
Paul R

Reputation: 212949

Simplest solution might be to bitwise AND the original string with a version of itself which has been shifted left or right by 1 bit. If the resulting bit string in non-zero then you have at least one 11 in there:

test = (src & (src << 1));

Upvotes: 15

Related Questions