Talk:Find first and last set bit of a long integer

More Clarification "set bit"

The example gives

INT: find first & last set bit  |LWB|UPB|Bits
                               0| 33| 32|0

How are there any set bits in an unsigned integer? --Dgamey 03:43, 8 December 2011 (UTC)

Clarification

The task is unclear in what number should be computed. It mentions "first" and "last" set bits, but with bits written in most-significant to least-significant order, or the other way around? (i.e. which of "upb" and "lwb" should compute the least significant set bit? and which computes the most significant set bit?) For a 32-bit integer should the least significant bit be numbered 0, 1, 31, or 32? Also, what values should be returned if there are no set bits? And for negative integers, should the most significant set bit be the sign bit?

The ALGOL example seems to indicate that: the least significant bit is numbered 32 (and the most significant bit is numbered 1). This seems the reverse of most people's bit numberings (where the least significant bit should be numbered 0, and the most significant 31), and also wouldn't make sense for arbitrary-precision integers (where would you start counting?). Also, it seems that "lwb" computes the most significant set bit, while "upb" computes the least significant set bit. Is this the example we should follow for other languages? --208.80.119.67 23:38, 7 December 2011 (UTC)

The whole thing doesn't make sense for multi-precision integers. If you are willing to use language/library bigint implementation, you basically willingly forfeit control over how it's done behind the scenes, it doesn't make sense to "efficiently find a set bit" -- who says the numbers are internally represented by bits to begin with? --Ledrug 00:30, 8 December 2011 (UTC)

/* Clarification */ integers are used in the test case only to conveniently supply binary specimen for testing.

re: This seems the reverse of most people's bit numberings.

C also - correct me if I am wrong - prints the most significant bit/octel/hex digit on the left, and the least on the extreme right, hence the operators << and >>. Also python, and most other programming languages display and (pretend to) store right to left. It's probably a human thing.

I was referring to the bit numbering, not how they are printed. From what I've seen, the least significant bit is usually numbered "0" and the most significant bit "31". --208.80.119.67 02:34, 8 December 2011 (UTC)

re: And for negative integers

The task is focused on binary/bits. Whether it is signed or unsigned is not so important. The test case requires only +ve. Beyond that just do the natural thing for the specific language & CPU.

re: wouldn't make sense for arbitrary-precision integers

Agreed. It does seem odd having the least significant bit at (algol68g's) 116 for long bits/long ints. Thus this could make Arbitrary Precision integers particularly weird. But this task is about bit manipulation. The test case happens to use long int. Maybe a particular language/CPU puts these in reverse. In such a case just find the location of first and last non zero bits on this platform. Try not to worry about what is being represented. Try not to worry about the significance of the actual bits.

Also: The task doesn't request for Arbitrary Precision bits per se, rather it asks for an algorithm that works 32 bits, and then another algorithm that works for any particular precision implementation. Hopefully his would not preclude an Arbitrary Width Bits algorithm. ¢ A 'not of 0 on Arbitrary Precision bits is going to be very interesting! :-) ¢

FYI: Algol68 permits the coercion/casting/widening of bits to a bool array, eg<lang algol68>[]BOOL bools a = 2r101,

      bools b = (TRUE,FALSE,TRUE); 

BITS bits c = 2r101,

    bits d = bits pack((TRUE,FALSE,TRUE)); # Hence ... #
    print((bits width ELEM bits a, []BOOL(bits a)[bits width])) # prints "1F" - the same last bit #</lang> Hence there are strong synergies between bits and []bool type, but they are not the same type.  Similarly the types int and bits are distinct and require explicit casting with the operators bin and abs.  C - by contrast - does not have this distinction, in C an int also happens to be bits.

Good luck, and Merry Xmas!

NevilleDNZ 02:02, 8 December 2011 (UTC)

Initial C code specimen requires a long int algorithm

The use of #define in the C code specimen works really well when unrolling a loop.

The code issues are:

• code specimen lacks any more generally algorithm that would work - for example - with 128, or 256 width bits.
• the code confuses "lowest set bit" (a bit order concept) with "least significant bit" (an integer concept). These are actually almost opposites on most machines.
• ditto for "upper set bit" and "most significant bit".
• the results are in hex eg. 0xc0ffee, not binary 0b110000001111111111101110 making it difficult to visually discover/confirm the results.

Try using Duff's device to unroll wider bits types.

A thought: maybe ( as C has given us << left shift and >> right shift ) this bits task should be asking for the first left bit set, and the first right bit set? This would be "type agnostic" avoiding confusion with integers arithmetic properties.

NJoy NevilleDNZ 03:17, 8 December 2011 (UTC)