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  
Share this Question
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  
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  
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 bitcount 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 bitbybit
check.
Chris  
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 offtopic 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 62 "Find First String
of 1Bits of a Given Length" in the book "Hacker's Delight" by Henry S.
Warren, Jr (AddisonWesley, 2003), as that sounds close to what you want
to do.
 Norbert  
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 offtopic 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 62 "Find First String of 1Bits of a Given Length" in the book "Hacker's Delight" by Henry S. Warren, Jr (AddisonWesley, 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  
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  
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  
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

EMail: Mine is a gmx dot de address.  
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  
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 shiftandtest
algorithm, since that's both simple and clear and it seems unlikely
that this is a performancecritical task. If the OP is determined
to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string.
2. Find the lowestorder 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 shiftandtest).

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

Michael Wojcik wrote: Given [the] requirements, I'd just implement a shiftandtest algorithm, since that's both simple and clear and it seems unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest).
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 nontrivial 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  
P: n/a

In article <11**********************@l41g2000cwc.googlegroups .com>,
Peter Nilsson <ai***@acay.com.au> wrote:
:Michael Wojcik wrote:
:> 1. Find the highestorder 1 bit in the candidate string.
:> 2. Find the lowestorder 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?  
P: n/a

Peter Nilsson wrote: Michael Wojcik wrote: Given [the] requirements, I'd just implement a shiftandtest algorithm, since that's both simple and clear and it seems unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest).
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 nontrivial 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  
P: n/a

Walter Roberson wrote: Peter Nilsson <ai***@acay.com.au> wrote: :Michael Wojcik wrote: :> 1. Find the highestorder 1 bit in the candidate string. :> 2. Find the lowestorder 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  
P: n/a

CBFalconer wrote: Peter Nilsson wrote:
Michael Wojcik wrote:
Given [the] requirements, I'd just implement a shiftandtest algorithm, since that's both simple and clear and it seems unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest).
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 nontrivial 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

EMail: Mine is an /at/ gmx /dot/ de address.  
P: n/a

CBFalconer wrote: Peter Nilsson wrote: Michael Wojcik wrote: Given [the] requirements, I'd just implement a shiftandtest algorithm, since that's both simple and clear and it seems
unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest).
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 nontrivial 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 shiftandtest", 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  
P: n/a

Peter Nilsson wrote: CBFalconer wrote: Peter Nilsson wrote: Michael Wojcik wrote:
Given [the] requirements, I'd just implement a shiftandtest algorithm, since that's both simple and clear and it seems unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest).
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 nontrivial 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 shiftandtest", 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  
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 shiftandtest", 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  
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  
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  
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 nonzero
= 1;
Chris  
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 nonzero
Logical negation (!) not bitwise complement (~).
= 0101b && 0;
= 0;
It works basically the same way as Peter Nilsson's: for nonzero 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  
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 shiftandtest algorithm, since that's both simple and clear and it seems unlikely that this is a performancecritical task. If the OP is determined to find a more complicated approach, though, I might suggest:
1. Find the highestorder 1 bit in the candidate string. 2. Find the lowestorder 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 shiftandtest). 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 nontrivial 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 "nonobvious", 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
reductioninstrength 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 shiftand
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  
P: n/a

Michael Wojcik wrote: "Peter Nilsson" <ai***@acay.com.au> writes: Michael Wojcik wrote: ... 2. Find the lowestorder 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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1846
 replies: 24
 date asked: Nov 14 '05
