Repository navigation
Add common bit twiddling operations for integers to core library. #6486
Description
This issue was originally filed by @mdakin
Some of the common bit twiddling hacks on integers (int32 and int64 versions?) are used quite frequently. A well tested implementation would be nice to have. They tend to be very simple and does not bloat the core library.
Some examples:
- Number of 1's in an int (There is already an open issue for this: http://code.google.com/p/dart/issues/detail?id=5798)
- Nearest power of 2
- Check if power of 2.
- Find highest/lowest one bit.
- Number of leading/trailing zeroes.
- Rotate left/right.
- Reverse bits.
- Reverse Bytes.
- Bit rank: Number of 1 bits from most significant bit down to the bit at position n.
- Gray code.
Activity
lrhn commentedon Nov 3, 2012
Some of these operations depend on a fixed number of bits (leading zeros, rotate, reverse). If these are desired, we should put them on a separate Int32/Int64 class.
The rest can be implemented on arbitrary precision integers too.
Removed Type-Defect label.
Added Type-Enhancement, Area-Library, Triaged labels.
rakudrama commentedon Nov 3, 2012
Putting operations only on a few select fixed width classes is too restrictive.
It does not allow code to be easily parameterized by the width.
e.g. a bit-reverse is useful with a N-bits parameter in FFT, at least in an assertion.
If there is a special class with a fixed width, like Int32 or Uint19 they obviously can support operations that depend on the number of bits.
But I think that all of the width-sensitive operations could be implemented on the int class with a width parameter, meaning extract the bottom W bits and then do the W-dependent operation on them.
To support the almost orthogonal issue of the sign, I suggest these width parameterized 'conversion' operations:
class int ... {
/// Returns the bottom [w] bits as an unsigned int.
int asUnsigned(int w);
/// Returns the bottom [w] bits as a signed int.
int asSigned(int w);
}
I would expect the compilers to have deep knowledge of these two operations and be able to compile
x = (x + 1).asUnsigned(8);
as
x = (x + 1) & 0xFF;
and something similar, but quite challenging at the source level, for x = (x + 1).asSigned(8);
(intel syntax x86: inc eax; movsx eax,al;)
(JS: var t = x + 1; x = (t & 0x7f) - (t & 0x80); or x = ((x + 1) << 24) >> 24;)
If we do have an Int64 class, it should also support the width-dependent operations for consistency with int.
ahmetaa commentedon Oct 23, 2017
Perhaps this can be reconsidered in Dart 2.0
gnudles commentedon Sep 2, 2021
So reverse the whole word and then shift by (WORDLENGTH - N)
No needed as seperate operation, just shift first and then use popcount.
From the list above, I think the most performance critical are
Reverse of full word (64 bit only),
PopCount (64 bit only)
byte swap is useful, but it might better be added to class ByteData
These two are the same, aren't they?
Number of leading/trailing zeroes is very important.
Not needed, It can be easily calculated with CTZ, CLZ (count trailing/leading zero)
Also "Check if power of 2."
2 Instruction instead of one is not such a big penalty, so it is not so important for now. Also it is useful to Rotate on N bits, but it will make implementation of Dart SDK to be more complex.
I'm not aware of any processor that supports this
These operation can't be used in JS, anyway.
[core] Add trailingZeroBitCount and oneBitCount to int
[vm] Recognize int.trailingZeroBitCount/oneBitCount as graph-inlinable
Revert "[vm] Recognize int.trailingZeroBitCount/oneBitCount as graph-…
Reland "[vm] Recognize int.trailingZeroBitCount/oneBitCount as graph-…
Revert "Reland "[vm] Recognize int.trailingZeroBitCount/oneBitCount a…
Reland "[vm] Recognize int.trailingZeroBitCount/oneBitCount as graph-…