Opened 11 years ago
Closed 7 years ago
#7656 closed enhancement (duplicate)
Bitset tricks
Reported by: | jason | Owned by: | tbd |
---|---|---|---|
Priority: | minor | Milestone: | sage-duplicate/invalid/wontfix |
Component: | misc | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | Jeroen Demeyer | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
Change History (14)
comment:1 Changed 11 years ago by
- Milestone changed from sage-4.4.2 to sage-wishlist
- Priority changed from major to minor
comment:2 Changed 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
- Description modified (diff)
comment:4 Changed 10 years ago by
- Description modified (diff)
comment:5 Changed 10 years ago by
- Description modified (diff)
comment:6 Changed 10 years ago by
- Description modified (diff)
comment:7 Changed 10 years ago by
comment:8 Changed 10 years ago by
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?
comment:9 Changed 10 years ago by
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
comment:10 Changed 10 years ago by
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
comment:11 Changed 7 years ago by
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".
comment:12 Changed 7 years ago by
- Milestone changed from sage-wishlist to sage-duplicate/invalid/wontfix
- Reviewers set to Jeroen Demeyer
- Status changed from new to needs_review
...and it's probably superseded by #16937 also.
comment:13 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:14 Changed 7 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
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