Re: 64-bit masks

[Robert Elz <kre%munnari.OZ.AU@localhost>]

    Date:        Fri, 27 Nov 2009 14:06:38 -0000
    From:        Sad Clouds <cryintothebluesky%googlemail.com@localhost>
    Message-ID:  <op.u3135aln8u90ff@localhost>

Others commented on the data type, etc.   On the code...

  | uint64_t current_state = state;
  | 
  | for(i=0; i<64; i++)
  | {
  |     current_state >>= i;

You most probably want >> 1 there, not >> i, or you get >> 0, >> 1, >> 2,
(in sequence), ie, if state started off as 0x1000, it is tested as 0x1000
0x800 0x200 x040 0x4 (as shifts of 0, 1, 2, 3, and 4 are applied in succession).

Then, you'd need to move the shift to after the test, so you don't just
drop the LSB.

Alternatively, what you were probably thinking was

        current_state = state >> i;

which would work, but means a lot of repeated shifting.

  |     if(current_state == (0xffffffffffffffffULL >> i))
  |             break; /* all objects are busy */

This is the wrong test in the wrong place - if it succeeds when i == 0,
(everything is busy) then it would be better tested outside the loop (if
you really believe this happens often enough that it is worth optimising
for).    if it doesn't happen when i==0, then unless the loop continues
after finding a free object, it can never succeed - in the case where you
are actually looking for all the free objects (rather than just finding one
thatis free), I suspect this optimisation costs so much to include (if it
doesn't short circuit the loop very early) and would gain so little, that
the code would run quicker (and be simpler and easier to understand) if
you just left this out.

The comment is also wrong (for the code as you had it), it should be
"all the remaining objects are busy"

  |     if((current_state & 0x1U) == 0)
  |             printf("object %d is free\n", i);

you don't really need the 'U' there (0x1U), it just makes it harder to read,
current_state is unsigned, so any arithmetic done on it is unsigned,
and a signed '1' and an unsigned '1' are the same thing...

Whether this is really an appropriate algorithm depends on just what you
need to know all the free objects for - if you just want to find the first
free object, there are easier (faster) ways, but if you really need to
find all of them, this might be OK.

kre