Interesting Quest - Any optimized way to find if consective one's exist in a word!

[Alex Fraser]

Peter Nilsson wrote: [snip]
int shafique(unsigned x)
{
unsigned u = x + x - (x & (x - 1));
unsigned v = u & (u - 1);
return x != 0 || v == 0;
}
ITYM: &&

Actually I didn't, but your correction is valid, and appropriate.

int shafique(unsigned x) {
return x && ((((-x & x) + x) & x) == 0);

Or even:
return x && !(((-x & x) + x) & x);

}

Alex

 

[Chris Williams]

Trying to determine if there are only consecutive bits:

Or even:
return x && !(((-x & x) + x) & x);

Eh? Putting a signed nibble (x = 5 = 0101b) in there:

0101b && !(((-0101b & 0101b) + 0101b) & 0101b);
= 0101b && !(((1011b & 0101b) + 0101b) & 0101b);
= 0101b && !((0001b + 0101b) & 0101b);
= 0101b && !(0110b & 0101b);
= 0101b && !0100b;
= 0101b && 1011b; //both non-zero
= 1;

-Chris

 

[Alex Fraser]

Trying to determine if there are only consecutive bits:


Eh? Putting a signed nibble (x = 5 = 0101b) in there:

It's unsigned. If the type of x has 4 value bits, -x is (mathematically)
2^4 - x. (But the result is the same for signed types using two's complement
representation.)

0101b && !(((-0101b & 0101b) + 0101b) & 0101b);
= 0101b && !(((1011b & 0101b) + 0101b) & 0101b);
= 0101b && !((0001b + 0101b) & 0101b);
= 0101b && !(0110b & 0101b);
= 0101b && !0100b;
= 0101b && 1011b; //both non-zero

Logical negation (!) not bitwise complement (~).

= 0101b && 0;
= 0;

It works basically the same way as Peter Nilsson's: for non-zero x, extract
the least significant set bit (-x & x), and add that to the original value.
If and only if the original value is of the required form, all the
originally set bits will now be clear (the carry propagates all the way to
the position of the most significant set bit), so the result of a bitwise
AND with the original value will be zero.

Alex

 

[Michael Wojcik]

Given [the] requirements, I'd just implement a shift-and-test
algorithm, since that's both simple and clear and it seems unlikely
that this is a performance-critical task. If the OP is determined
to find a more complicated approach, though, I might suggest:

1. Find the highest-order 1 bit in the candidate string.
2. Find the lowest-order 1 bit in the candidate string.
3. Shift the string to the right so that the bit from step 2 is
in the 0 position.
4. Compare the result with 2**length - 1.

IIRC, there are algorithms for performing steps 1 and 2 in non-
obvious ways (ie other than by shift-and-test).

Anyone with a copy of K&R2 can find out how to do 2 for unsigned
integers.

Yes, I was just too lazy to look it up, so I threw in a standard
qualification.

However 1 will prove much more difficult for non-trivial values.
It's effectively a log2 calculation. It can be done assuming a
fixed width integer type by using a hashed array lookup

Certainly. It can be done with cascading comparisons, too. I'm
not sure I'd count those as "non-obvious", but clearly that's a
subjective judgement.

Note that the simplest way to do step 3, if you only have a mask
for the bottom bit, is to actually use a division.

I don't see how that's simpler than a shift. Same number of
operators and operands, and any decent compiler will do the
reduction-in-strength to the faster operation anyway.

If the OP is
not working with constants, this may prove way more inefficient
than simply shift testing.

Of course, which was one reason why I said I'd just use shift-and-
test.

One method to do the OP's task (posted elsethread) is to determine
the lowest set bit, add it to the original, and check the result
consists of a single bit.

Yes. That hadn't occurred to me.

--
Michael Wojcik (e-mail address removed)

Painful lark, labouring to rise!
The solemn mallet says:
In the grave's slot
he lies. We rot. -- Basil Bunting

 

[Peter Nilsson]

I don't see how that's simpler than a shift. Same number of
operators and operands, ...

What I was thinking of was...

unsigned divide_out_twos(unsigned x)
{
unsigned m = x & -x;
if (m) x /= m;
return x;
}