1

For a hot loop in an arithmetic tool I need to make the trade-off between keeping the index of the lowest bit of a struct's element in memory, or looking it up when necessary. Keeping it in memory works but is clunky. Dropping the field is limited by how fast I can do this instead;

inline bool operator< (const unsigned long& lhs, const unsigned long& rhs) {
    unsigned long left, right;

    _BitScanForward(&left , lhs);
    _BitScanForward(&right, rhs);

    return left < right;
}

(Simplified). So 2 < 4, but 2 == 6. I'm wondering if there's an easier way of extracting this info.

Meeuwisse
  • 157
  • 6

1 Answers1

1

If the index is less, then two to the power that index is also less (and vice versa). So you can extract it and compare the lowest bit by magnitude instead of by index:

lsleft = lhs & -lhs;
lsright = rhs & -rhs;
return lsleft < lsright;

As a bonus, this also doesn't die if the input is zero.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Given that the OP is using `unsigned long` values, would it not be necessary (or better, or cleaner) to calculate `isleft = lhs & ((~lhs)+1)` to simulate two's complement? – mindriot Feb 22 '16 at 16:53
  • @mindriot no, negation on unsigned things is defined appropriately (for example, see [this question](http://stackoverflow.com/q/8026694/555045)). It is rather for signed types that this would be dangerous. – harold Feb 22 '16 at 16:54
  • thanks, didn't know that. That leaves the pathological [cases with non-two's-complement representations](http://stackoverflow.com/questions/12276957/are-there-any-non-twos-complement-implementations-of-c) ;) – mindriot Feb 22 '16 at 16:57
  • Doing this with signed types is trouble anyway, even when it "works" (two's complement negation is used) it leaves INT_MIN as a special case.. – harold Feb 22 '16 at 17:01