Bitset tricks

[jason]

There are some extra tricks in here: ​http://www.jjj.de/fxt/#fxtbook

in the first chapter for doing bitset operations that ought to be applied to our Bitset class. For example, there is a trick that allows you to count the number of bits in log time instead of linear time.

More bitset tricks can be found at:

• ​The Aggregate Magic Algorithms by Hank Dietz
• ​Bit Twiddling Hacks by Sean Eron Anderson
• ​All The Twiddled Bits by Stephan Brumme

The project on this ticket can be divided up into the following sub-projects:

1. #10287 memleak in bitset_realloc()
2. #10093 clean up documentation of sage/misc/bitset.pyx
3. #10269 clean up documentation of sage/misc/bitset_pxd.pxi
4. #10245 clean up documentation of sage/misc/bitset.pxi

[ncohen]

This FXTBook is the best book in the universe. I'm *EAGER* to read it.

About the counting trick : there is a builtin gcc command called builtin_popcount which may do wonders. It does count the bits in general (though I haven't found the corresponding code) -- it may well be the logarithmic way (+very nice trick btw), and in case the popcnt instruction is available on the processor, it is directly called.

And I assure you for having compared the two that it does.... WONDERS :-D

Nathann

[jason]

If we can guarantee that gcc is used to compile the file, then great! I think we can assume that for now, but it may not be true in the future. Is there a preprocessor check we can put in or something?

[ncohen]

I'd say "test for GNUC with the preprocessor". Though on these aspects I'd ask David first :-D

​http://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html

Nathann

[ncohen]

Oh. Actually I already did and he advised to use this very piece of code

#ifdef __GNUC__
 /* Make use of GCC extensions here. */
#else
/* Add portable version here */
#endif

Give to Caesar .. :-)

Nathann

[jdemeyer]

This ticket is very vague. It should either be made more concrete (like, what do you want to do with bitsets) or closed as "invalid".

[jdemeyer]

...and it's probably superseded by #16937 also.