add bitLength / bitCount method to int type

[gamato]

Bit-length is the number of binary digits, called bits, necessary to represent an integer in the binary number system.

It seems bitLength() is better (that is more standard) name than bitCount() -- https://en.wikipedia.org/wiki/Bit-length

[gamato]

Here's a simple implementation:

int bit_length (int i) {
    if (i == 0)
        return 0;
    return int(logb(i))+1;
}

This would likely fail for large numbers, though, due to loss of digits / precision in float calculations.

[davidnich]

should this return a value rounded up to a power of 2 or the exact bit length - for example, should 7.bitLength() return 3 or 4?

[gamato]

                                                                                  Exact bit length - 7 should return 3.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        From: David NicholsSent: sobota, 21. mája 2016 7:07To: qorelanguage/qoreReply To: qorelanguage/qoreCc: gamato; AuthorSubject: Re: [qorelanguage/qore] add bitLength / bitCount method to int type (#874)should this return a value rounded up to a power of 2 or the exact bit length - for example, should 7.bitLength() return 3 or 4?

—You are receiving this because you authored the thread.Reply to this email directly or view it on GitHub

[tethal]

We also need to define the behavior of such function for negative numbers. Also note that in a system with two's complement signed numbers (which qore is), the number of bits necessary to represent 7 is actually 4, not 3.

[davidnich]

@tethal I agree about negative numbers; I was thinking about this myself - if you say that in 2's complement you need the extra high bit as zero to show that it's a positive number, then you are correct - maybe however we should implement .bitLength() to return the bit position of the highest bit set in the number (which would always be 64 for all negative integers, so basically useless for negative numbers, but would be 3 for 7 for example) - not sure...

[tethal]

That's definitely an option. Another way would be to return the position of the bit that is different from the sign bit (I think this is the closest to Java's BigInteger.bitLength). Or we can stick to the 'logarithm definition' above and throw an exception for negative numbers. Or we can return the bit length of the absolute value of the argument (we'd just have to be careful about the extreme (-2^63) whose absolute value does not fit into a signed 64 bit integer). Anyway, there's a lot of options and I don't really have a favorite.

[gamato]

Hi. I think sign is usually not considered or numbers are converted (abs()-ed, negative numbers bit-flipped, etc). Looking at Wolfram Alpha (http://reference.wolfram.com/language/ref/BitLength.html) and Python (https://docs.python.org/3/library/stdtypes.html#int.bit_length) show two different approaches. Wolfram bitflips negative input while Python discards the sign. Thus bitLength() of -1 is 0 in Wolfram and 1 in Python, while bitLength() of -8 is 3 in Wolfram and 4 in Python. I'm not sure which one is better for us, but bit_length() is usually meant for positive (or unsigned) integers or binary data (bit strings).

Btw, we could have both bitLength() and bitCount(). The latter would count set bits in integers (or bits different from sign?).

Btw, bitCount() and BitLength() would be useful for binary type, too.

[gamato]

Perhaps we can implement both functions for non-negative integers now and leave implementation for negative integers until we know better what our needs are. And perhaps we could implement both functions for binary type too. What do you think ?

[tethal]

I don't know what you mean - the function has to do something for negative numbers. Anyway, Wolfram's approach seems to produce equivalent results as Java's, so Python has been outvoted :-)

My proposal then is:

• add <int>::bitLength() which will return the number of bits needed to represent the value excluding the sign bit (which is the same as the position of the first bit that is different from the sign bit, which means that it simply flips all bits in negative numbers before the calculation):
  • 4.bitLength() = 3
  • 3.bitLength() = 2
  • 2.bitLength() = 2
  • 1.bitLength() = 1
  • 0.bitLength() = 0
  • -1.bitLength() = 0
  • -2.bitLength() = 1
  • -3.bitLength() = 2
• add <int>::bitCount() which will return the number of bits different from the sign bit - again, simply flips the bits if the input is negative, so that both functions handle negative numbers consistently
  • 4.bitCount() = 1
  • 3.bitCount() = 2
  • 2.bitCount() = 1
  • 1.bitCount() = 1
  • 0.bitCount() = 0
  • -1.bitCount() = 0
  • -2.bitCount() = 1
  • -3.bitCount() = 1
• keep this issue just for ints and move the discussion of 'whether or not we should do this also for binary' to #889

[gamato]

What I meant is that function can be implemented (and documented) for i>=0 and would throw an error for negative input values. Later, when we figure out what is better for negative values, we can implement that.