By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,569 Members | 1,358 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,569 IT Pros & Developers. It's quick & easy.

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

P: n/a
Hello,

Can anybody have idea as how to find it there exist consective one's in
a word/dword using bitwise operatiors in C language.

Obviously this can be done by shifting and looping one by one; but
there must be some faster way of doing it.

The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword. e.g. 0000b has no consective
ones.... 00011000b has two consective ones, 0001101... has no
consective ones 000001000 has one consective one! So the requiement is
to find out if there exists any 0 sandwitched between two ones.

Best Regards,
Shafique

Nov 14 '05 #1
Share this Question
Share on Google+
24 Replies


P: n/a
shafique wrote:
Can anybody have idea as how to find it there exist consective one's in a word/dword using bitwise operatiors in C language.
Shift one and and.

The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword. e.g. 0000b has no consective
ones.... 00011000b has two consective ones, 0001101... has no
consective ones 000001000 has one consective one! So the requiement is to find out if there exists any 0 sandwitched between two ones.


Errors are abundant in this paragraph (if the first paragraph is
right).

Daniel Vallstrom

Nov 14 '05 #2

P: n/a
"shafique" <ne***********@lycos.co.uk> wrote in message
news:11*********************@l41g2000cwc.googlegro ups.com...
Can anybody have idea as how to find it there exist consective one's in
a word/dword using bitwise operatiors in C language.
I infer from your (snipped) examples that what you really want to determine
is whether or not the value is of the form (2^n - 1) * 2^m, where n and m
are integers with n > 0 and m >= 0 ('^' denotes exponentiation, not the C
XOR operator). It's not clear if you need to know what n and/or m are.

Please clarify.
Obviously this can be done by shifting and looping one by one; but
there must be some faster way of doing it.


Probably.

Alex
Nov 14 '05 #3

P: n/a
> Can anybody have idea as how to find it there exist consective one's
in
a word/dword using bitwise operatiors in C language.

Obviously this can be done by shifting and looping one by one; but
there must be some faster way of doing it.

The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword. e.g. 0000b has no consective
ones.... 00011000b has two consective ones, 0001101... has no
consective ones 000001000 has one consective one! So the requiement is to find out if there exists any 0 sandwitched between two ones.


I suspect that if you find the bit-count algorithm that only uses bit
shifts and masks and then figure out how and why it works, you may be
able to come up with something that fits your specification.
Personally, the best I can do is:

#define BAD 0
#define ALL_ZERO 1
#define MIDDLE 2
#define LEFT 4
#define RIGHT 8
#define BOTH 12 //Bit mask covering LEFT and RIGHT

int onlyHasConsecutiveBits(int test) { //returns 0 if bad, 1 if good
int L;
int possibilities[] = {
ALL_ZERO, //0000
RIGHT, //0001
MIDDLE, //0010
RIGHT, //0011
MIDDLE, //0100
BAD, //0101
MIDDLE, //0110
RIGHT, //0111
LEFT, //1000
BAD, //1001
BAD, //1010
BAD, //1011
LEFT, //1100
BAD, //1101
LEFT, //1110
BOTH //1111
};

int previouslyFound = ALL_ZERO;
int wasGap = 0;
for (L = 0; L < 8; L++) {
int result = possibilities[test & 0xf];
test >>= 4;

switch (result) {
case BAD:
return 0;
case RIGHT:
case BOTH:
if (
(previouslyFound != ALL_ZERO && !(previouslyFound & LEFT))) ||
wasGap
) {
return 0;
}
break;
case LEFT:
case MIDDLE:
if (previouslyFound != ALL_ZERO) {
return 0;
}
break;
case ALL_ZERO:
if (previouslyFound != ALL_ZERO) {
wasGap = 1;
}
break;
}
if (result != ALL_ZERO) {
previouslyFound = result;
}
}

if (previouslyFound == ALL_ZERO) {
return 0;
}
return 1;
}

which I just wrote in there, so it probably will have bugs and typos
and such. But such a method will at least be better than a bit-by-bit
check.

-Chris

Nov 14 '05 #4

P: n/a
"shafique" <ne***********@lycos.co.uk> wrote in message news:11*********************@l41g2000cwc.googlegro ups.com...
[...]
Can anybody have idea as how to find it there exist consective one's in
a word/dword using bitwise operatiors in C language.

Obviously this can be done by shifting and looping one by one; but
there must be some faster way of doing it.

The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword. e.g. 0000b has no consective
ones.... 00011000b has two consective ones, 0001101... has no
consective ones 000001000 has one consective one! So the requiement is
to find out if there exists any 0 sandwitched between two ones.

[...]

Please note that your question is off-topic in comp.lang.c. This group
is for discussing ANSI C, not algorithms. A more appropriate newsgroup
for your question seems to be comp.programming.

It is a bit unclear exactly what the algorithm you are looking for is
supposed to do. You may want to look up section 6-2 "Find First String
of 1-Bits of a Given Length" in the book "Hacker's Delight" by Henry S.
Warren, Jr (Addison-Wesley, 2003), as that sounds close to what you want
to do.
-- Norbert
Nov 14 '05 #5

P: n/a
Norbert Juffa wrote:
"shafique" <ne***********@lycos.co.uk> wrote in message
[...]
Can anybody have idea as how to find it there exist consective
one's in a word/dword using bitwise operatiors in C language.

Obviously this can be done by shifting and looping one by one;
but there must be some faster way of doing it.

The thing I want is to define some masks and macros and find if
there are consective ones on a word/dword. e.g. 0000b has no
consective ones.... 00011000b has two consective ones, 0001101...
has no consective ones 000001000 has one consective one! So the
requiement is to find out if there exists any 0 sandwitched
between two ones. [...]

Please note that your question is off-topic in comp.lang.c. This
group is for discussing ANSI C, not algorithms. A more
appropriate newsgroup for your question seems to be
comp.programming.


Disagree. He is looking for a C snippet to perform a certain task.

It is a bit unclear exactly what the algorithm you are looking
for is supposed to do. You may want to look up section 6-2 "Find
First String of 1-Bits of a Given Length" in the book "Hacker's
Delight" by Henry S. Warren, Jr (Addison-Wesley, 2003), as that
sounds close to what you want to do.


He probably wants to optimize multiplication by a constant. If the
constant consists of a single run of 1 bits, the operation consists
of subtracting two shifted versions of the other operand. Not as
useful as it used to be.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #6

P: n/a
In article <11*********************@l41g2000cwc.googlegroups. com>,
ne***********@lycos.co.uk says...
The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword.
Splitting these up...
e.g. 0000b has no consective ones....
Ok.

00011000b has two consective ones,
Ok.

0001101... has no consective ones
Explain this one please.

000001000 has one consective one!
I see this one.

So the requiement is to find out if there exists any 0 sandwitched
between two ones.


That sounds like a different requirement. Note that 01010101b fits
that requirement, but does not seem to fit what you have written above,
apart from the one which I asked for an explanation on.

--
Randy Howard (2reply remove FOOBAR)
"Making it hard to do stupid things often makes it hard
to do smart ones too." -- Andrew Koenig
Nov 14 '05 #7

P: n/a
shafique wrote:
Hello,

Can anybody have idea as how to find it there exist consective
one's in a word/dword using bitwise operatiors in C language. ^^^^^^^^^^
If you want an implementation specific answer, ask in an
implementation specific group.
Obviously this can be done by shifting and looping one by one;
but there must be some faster way of doing it.
What do you mean by 'fast'?
The thing I want is to define some masks and macros and find if
there are consective ones on a word/dword. e.g. 0000b has no
consective ones.... 00011000b has two consective ones, 0001101...
has no consective ones 000001000 has one consective one! So the
requiement is to find out if there exists any 0 sandwitched
between two ones.


int shafique(unsigned x)
{
unsigned u = x + x - (x & (x - 1));
unsigned v = u & (u - 1);
return x != 0 || v == 0;
}

--
Peter

Nov 14 '05 #8

P: n/a


Peter Nilsson wrote:
shafique wrote:
Hello,

Can anybody have idea as how to find it there exist consective
one's in a word/dword using bitwise operatiors in C language.
^^^^^^^^^^
If you want an implementation specific answer, ask in an
implementation specific group.

Obviously this can be done by shifting and looping one by one;
but there must be some faster way of doing it.

What do you mean by 'fast'?

The thing I want is to define some masks and macros and find if
there are consective ones on a word/dword. e.g. 0000b has no
consective ones.... 00011000b has two consective ones, 0001101...
has no consective ones 000001000 has one consective one! So the
requiement is to find out if there exists any 0 sandwitched
between two ones.

int shafique(unsigned x)
{
unsigned u = x + x - (x & (x - 1));
unsigned v = u & (u - 1);
return x != 0 || v == 0;

ITYM: &&
Otherwise, you will always get 1 as return value. }


Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

Nov 14 '05 #9

P: n/a
Michael Mair wrote:
Peter Nilsson wrote:
shafique wrote:
The thing I want is to define some masks and macros and
find if there are consective ones on a word/dword. e.g.
0000b has no consective ones.... 00011000b has two
consective ones, 0001101... has no consective ones
000001000 has one consective one! So the requiement is
to find out if there exists any 0 sandwitched between
two ones.


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.

--
Peter

Nov 14 '05 #10

P: n/a

In article <MP************************@news.verizon.net>, Randy Howard <ra*********@FOOverizonBAR.net> writes:
In article <11*********************@l41g2000cwc.googlegroups. com>,
ne***********@lycos.co.uk says...
The thing I want is to define some masks and macros and find if there
are consective ones on a word/dword.


Splitting these up...
e.g. 0000b has no consective ones....


Ok.

00011000b has two consective ones,


Ok.

0001101... has no consective ones


Explain this one please.


I believe the OP means "if, in a string of bits, all the 1 bits are
consecutive, return the length of the substring of 1 bits; otherwise
return 0".

Thus the previous example evaluates to 0 because not all 1 bits are
consecutive.

That's the only interpretation I could find which fit all of his
examples.

Given those 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).

--
Michael Wojcik mi************@microfocus.com

I would never understand our engineer. But is there anything in this world
that *isn't* made out of words? -- Tawada Yoko (trans. Margaret Mitsutani)
Nov 14 '05 #11

P: n/a
Michael Wojcik wrote:

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. As a corollary of 2, it's trivial to establish that an
unsigned number consists of a single set bit.

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 (Lawrence
Kirby once posted a sample.) Whilst ingenious, it's not that
'obvious'. And it requires a multiplication.

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. If the OP is
not working with constants, this may prove way more inefficient
than simply shift testing.

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.

--
Peter

Nov 14 '05 #12

P: n/a
In article <11**********************@l41g2000cwc.googlegroups .com>,
Peter Nilsson <ai***@acay.com.au> wrote:
:Michael Wojcik wrote:
:> 1. Find the highest-order 1 bit in the candidate string.
:> 2. Find the lowest-order 1 bit in the candidate string.

:Anyone with a copy of K&R2 can find out how to do 2 for unsigned
:integers. As a corollary of 2, it's trivial to establish that an
:unsigned number consists of a single set bit.

I just looked through my copy of K&R2, and I don't see anything
aking to what you say -- at least not other than in the sense
of it describing bitwise operators and loop structures and so provides
all the elements needed to do the operations "the hard way".
Could I ask you to be more specific about which section you are
referring to?
--
How does Usenet function without a fixed point?
Nov 14 '05 #13

P: n/a
Peter Nilsson wrote:
Michael Wojcik wrote:

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. As a corollary of 2, it's trivial to establish that an
unsigned number consists of a single set bit.

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 (Lawrence
Kirby once posted a sample.) Whilst ingenious, it's not that
'obvious'. And it requires a multiplication.


How about:

#include <limits.h>
unsigned long msb = ULONG_MAX - LONG_MAX;
while (msb > x) msb >>= 1;

I don't think that has any portability problems.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #14

P: n/a
Walter Roberson wrote:
Peter Nilsson <ai***@acay.com.au> wrote:
:Michael Wojcik wrote:
:> 1. Find the highest-order 1 bit in the candidate string.
:> 2. Find the lowest-order 1 bit in the candidate string.

:Anyone with a copy of K&R2 can find out how to do 2 for unsigned
:integers. As a corollary of 2, it's trivial to establish that an
:unsigned number consists of a single set bit.

I just looked through my copy of K&R2, and I don't see anything
aking to what you say ... Could I ask you to be more specific about
which section you are referring to?


Exercise 2.9

--
Peter

Nov 14 '05 #15

P: n/a
CBFalconer wrote:
Peter Nilsson wrote:
Michael Wojcik wrote:
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. As a corollary of 2, it's trivial to establish that an
unsigned number consists of a single set bit.

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 (Lawrence
Kirby once posted a sample.) Whilst ingenious, it's not that
'obvious'. And it requires a multiplication.

How about:

#include <limits.h>
unsigned long msb = ULONG_MAX - LONG_MAX;
while (msb > x) msb >>= 1;

I don't think that has any portability problems.


Hmm, C99, 6.2.6.2, does not specify that the width of a signed
integer type and the corresponding unsigned integer type
has to be the same and the description of <limits.h> refers
only to 5.2.4.2.1 (Numerical limits for the sizes of integer
types) -- so how do we know that LONG_MAX==ULONG_MAX/2?
I'd rather use the latter (or ULONG_MAX>>1 if you like that
better) than relying on this relationship.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 14 '05 #16

P: n/a
CBFalconer wrote:
Peter Nilsson wrote:
Michael Wojcik wrote:

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. As a corollary of 2, it's trivial to establish that an
unsigned number consists of a single set bit.

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 (Lawrence
Kirby once posted a sample.) Whilst ingenious, it's not that
'obvious'. And it requires a multiplication.


How about:

#include <limits.h>
unsigned long msb = ULONG_MAX - LONG_MAX;
while (msb > x) msb >>= 1;

I don't think that has any portability problems.


The criteria was "other than by shift-and-test", but your msb
does have problems in that it could theoretically have the
values like 0 or 0xF8000000. But getting the top the top bit
of an unsigned integer type is quite simple, given that
assigning -1 will always produce the _MAX value.

The shift test for unsigned integers is simply...

unsigned_integer m = -1;
for (m = m/2+1; m; m >>= 1) if (x & m) break;
return m;

--
Peter

Nov 14 '05 #17

P: n/a
Peter Nilsson wrote:
CBFalconer wrote:
Peter Nilsson wrote:
Michael Wojcik wrote:

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. As a corollary of 2, it's trivial to establish that an
unsigned number consists of a single set bit.

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 (Lawrence
Kirby once posted a sample.) Whilst ingenious, it's not that
'obvious'. And it requires a multiplication.
How about:

#include <limits.h>
unsigned long msb = ULONG_MAX - LONG_MAX;
while (msb > x) msb >>= 1;

I don't think that has any portability problems.


The criteria was "other than by shift-and-test", but your msb
does have problems in that it could theoretically have the
values like 0 or 0xF8000000. But getting the top the top bit


It can't have a 0 value. unsigned must have at least one more
value bit than signed.
of an unsigned integer type is quite simple, given that
assigning -1 will always produce the _MAX value.

The shift test for unsigned integers is simply...

unsigned_integer m = -1;
for (m = m/2+1; m; m >>= 1) if (x & m) break;
return m;


I was using unsigned long so the routine could test any flavor of
unsigned x. However, with your initialization (I admit mine looks
slightly suspicious) and my loop, we have:

unsigned long msb = -1;
msb = msb/2 +1;
while (msb > x) msb /= 2; /* we don't HAVE to shift */

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Nov 14 '05 #18

P: n/a
CBFalconer wrote:
Peter Nilsson wrote:
CBFalconer wrote:

#include <limits.h>
unsigned long msb = ULONG_MAX - LONG_MAX;
while (msb > x) msb >>= 1;

I don't think that has any portability problems.


The criteria was "other than by shift-and-test", but your msb
does have problems in that it could theoretically have the
values like 0 or 0xF8000000. But getting the top the top bit


It can't have a 0 value. unsigned must have at least one more
value bit than signed.


No. Unsigned types only nead _at least_ the same number of value
bits as the corresponding signed type.

C99 6.2.6.2p2

"For signed integer types, the bits of the object representation
shall be divided into three groups: value bits, padding bits, and
the sign bit. ... (if there are M value bits in the signed type
and N in the unsigned type, then M <= N)."

Note M == N is explicitly allowed.
of an unsigned integer type is quite simple, given that
assigning -1 will always produce the _MAX value.

The shift test for unsigned integers is simply...

unsigned_integer m = -1;
for (m = m/2+1; m; m >>= 1) if (x & m) break;
return m;


I was using unsigned long so the routine could test any flavor of
unsigned x. However, with your initialization (I admit mine looks
slightly suspicious) and my loop, we have:

unsigned long msb = -1;
msb = msb/2 +1;
while (msb > x) msb /= 2; /* we don't HAVE to shift */


I would be particularly dissapointed if a compiler did not
optimise this to a shift operation. If it didn't, then the
division would likely be considerably more expensive, time-
wise, than a shift!

But I admit you are literally correct, your method doesn't
use a shift. :-) However, it is still O(N) with regards to
the number of operators applied.

--
Peter

Nov 14 '05 #19

P: n/a
"Peter Nilsson" <ai***@acay.com.au> wrote in message
news:11*********************@l41g2000cwc.googlegro ups.com...
Michael Mair wrote:
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);
}

Alex
Nov 14 '05 #20

P: n/a
"Alex Fraser" <me@privacy.net> wrote in message
news:37*************@individual.net...
"Peter Nilsson" <ai***@acay.com.au> wrote in message
news:11*********************@l41g2000cwc.googlegro ups.com...
Michael Mair wrote:
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
Nov 14 '05 #21

P: n/a
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

Nov 14 '05 #22

P: n/a
"Chris Williams" <th********@yahoo.co.jp> wrote in message
news:11*********************@c13g2000cwb.googlegro ups.com...
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:


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
Nov 14 '05 #23

P: n/a

In article <11**********************@l41g2000cwc.googlegroups .com>, "Peter Nilsson" <ai***@acay.com.au> writes:
Michael Wojcik wrote:

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 mi************@microfocus.com

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

P: n/a
Michael Wojcik wrote:
"Peter Nilsson" <ai***@acay.com.au> writes:
Michael Wojcik wrote:
...
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.


...
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, ...


What I was thinking of was...

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

--
Peter

Nov 14 '05 #25

This discussion thread is closed

Replies have been disabled for this discussion.