432,569 Members | 1,358 Online
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
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" 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" 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" 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 consectiveone'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 ifthere are consective ones on a word/dword. e.g. 0000b has noconsective ones.... 00011000b has two consective ones, 0001101...has no consective ones 000001000 has one consective one! So therequiement is to find out if there exists any 0 sandwitchedbetween 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 , Randy Howard 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 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 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 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-testalgorithm, since that's both simple and clear and it seems unlikelythat this is a performance-critical task. If the OP is determinedto 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 unsignedintegers. As a corollary of 2, it's trivial to establish that anunsigned 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 afixed width integer type by using a hashed array lookup (LawrenceKirby once posted a sample.) Whilst ingenious, it's not that'obvious'. And it requires a multiplication. How about: #include 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 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 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 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 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" 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" wrote in message news:37*************@individual.net... "Peter Nilsson" 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" 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" 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" 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