Minimum number of bits to hold a value +Log base-n

Community Forums/General Help/Minimum number of bits to hold a value +Log base-n

TomToad

(Posted 2016) [#1]

Not sure where to put this, so I put it here. I had a need to know what the minimum number of bits required to hold a certain value. I discovered that the formula is bits = Floor(Log2(Value))+1.

Nice, except that there is no Log base-2 command in BlitzMax. So a little more searching, and I found this. Log-n = Log(Value)/Log(n), So to get a base-2 logarithm, you just use this in BlitzMax Log2 = Log(Value)/Log(2)

Now to calculate the minimum number of bits, I just plug that into the above and get MinBits = Int(Log(Value)/Log(2))+1.

Nice thing is that this can be used for any base. To calculate the minimum number of hex digits needed, just replace 2 with 16. Number of bytes? Replace with 256.

Matty

(Posted 2016) [#2]

Well done.

TomToad

(Posted 2016) [#3]

A couple of functions and example
BlitzMax:

Function logN:Double(Value:Double,Base:Int=2)
	Return Log(Value)/Log(Base)
End Function

Function MinDigits:Int(Value:Int,Base:Int = 2)
	If Value = 0 Then Return 0
	Return Int(LogN(Value,Base))+1
End Function

Local n:Int = 65535
While n > 0
	Print "~nValue = "+n
	Print "minimum bits = "+MinDigits(n,2)
	Print "Minimum Hex Digits = "+MinDigits(n,16)
	Print "Minimum Bytes = "+MinDigits(n,256)
	Print "Minimum Shorts = "+MinDigits(n,65536)

	n = Input("New Value (0 to exit)? ").ToInt()
Wend

BlitzPlus and Blitz3D

Function logN#(Value#,Base%)
	Return Log(Value)/Log(Base)
End Function

Function MinDigits%(Value%,Base%)
	If Value = 0 Then Return 0
	Return Floor(LogN(Value,Base))+1
End Function

Local n% = 65535
While n > 0
	Print ""
	Print "Value = "+n
	Print "minimum bits = "+MinDigits(n,2)
	Print "Minimum Hex Digits = "+MinDigits(n,16)
	Print "Minimum Bytes = "+MinDigits(n,256)
	Print "Minimum Shorts = "+MinDigits(n,65536)

	n = Input("New Value (0 to exit)? ")
Wend

Kryzon

(Posted 2016) [#4]

You can add it to the code archives. Maybe Algorithms category (based on the description of that category):
http://www.blitzbasic.com/codearcs/codearcs.php