-1

I'm writing a boardgame engine and I wrote a 10x10 bitboard class. The class holds an array of two uint64's and implements various bit operations. An important operation I didn't implement yet is lsb(). I know that I can do lsb() on the first integer and if it's 0 do it on the second. However, checking if it's 0 seems redundant. What would be the most efficient way to implement lsb()?

EDIT: My current code is:

char s = lsb64(b_[0]);
if (s == 0 && b_[1] != 0) {
    s = lsb64(b_[1]) + 64;
}
return s;

lsb64() here returns 1 + the index of the bit

Are there performance improvements I could make? Note the if condition will almost always be false.

Flowers
  • 191
  • 1
  • 9
  • 2
    Show what you have done (or would try) and explain why you are not satisfied with it. – jxh Aug 30 '15 at 22:21
  • Assuming the first value is the least significant, you'd need to do some kind of test on it, surely? – Neil Kirk Aug 30 '15 at 22:22
  • @NeilKirk Yeah, I'm just not sure if testing if the first number is equal to 0 is the best way. – Flowers Aug 30 '15 at 22:24
  • @jxh So the obvious approach to me is to use one of the various methods to do lsb() on the first integer, then check if the number was 0 to decide if you need to do lsb() on the second number. – Flowers Aug 30 '15 at 22:27
  • 2
    As it is, you have not illustrated any effort on your part why you feel your hypothetical implementation is not acceptable. – jxh Aug 30 '15 at 22:30
  • @jxh Are you saying it is acceptable? I just don't understand cpu instructions well enough to know if that would be the best approach. – Flowers Aug 30 '15 at 22:40
  • It isn't clear what you're asking and you haven't exhibited anything to critique. The least significant bit of any multi-precision integer is given by (`lsb & 1)` where `lsb` is the least significant byte: there is no reason to test more than one value. Do you mean 'lowest *set* bit'? which is a completely different thing? – user207421 Aug 31 '15 at 01:38
  • @EJP Yes, that's what I mean – Flowers Aug 31 '15 at 02:12

1 Answers1

0

If you expect most inputs to have the bit set in the lower 64 bits, you will have to profile the execution. The following avoids two lsb64 calls.

return b_[0] ? lsb64(b_[0]) : (b_[1] ? 64 + lsb64(b_[1]) : 0);

Possible solutions to lsb64 can be found in a related question.

Community
  • 1
  • 1
jxh
  • 69,070
  • 8
  • 110
  • 193
  • Thanks. Actually, by far most inputs will have a bit set in the lower integer. Does that mean the upper solution will be faster? – Flowers Aug 30 '15 at 22:48
  • Why do you check for x = 0 after looking for the lsb in x? – Neil Kirk Aug 30 '15 at 22:51
  • @NeilKirk Apparently there's a builtin function in gcc, __builtin_ffs, which returns one plus the lsb index and 0 if it's 0. – Flowers Aug 30 '15 at 22:55