MS Excel Checking Bit Positions in Bytes and other stuff...

The other day I wanted to make a chart that showed all the numbers up to 255 sorted by the number of bits that are set to 1. Why I wanted to do this I can't remember but I manged to make a chart like that in MS Excel.  I also wanted to make a spreadsheet that would show me all the 1 bit differences from any 8 bit number, all the 2 bit differences, all the 3 bit differences and so on... What I'm writing about is how I went about doing that.

  

MS Excel pretty much sucks when it comes to dealing with binary numbers. The "=dec2bin()" doesn't work for a useful number of bits and there are no logical operators that you can use directly from Excel. Also there are no parity checking commands or functions that are built in to the spreadsheets. What I wanted to do specifically for my first chart was take a decimal number, convert it to a binary number then count the number of bits that are set to 1 in that number. After I figured out how many 1's there were in the number I wanted to put that number into a list.

  

For the second chart (or set of charts) that I wanted to make I needed to get a number, do a logical Exclusive Or with another number and then count the number of bits. Anyway here is a neat picture that shows what I came up with to do both of these things.

 

16 Bit dec2bin() and Parity in Excel

I wrote here about all this stuff before in another post that pretty much just explained how to do this but didn't have any examples of how to use it. This post will have some examples of how it all works.

On the top in the above picture is how the spreadsheet looks (or is supposed to look) and on the bottom the "show formulas" is turned on so you can see what is in the cells. With the exception of the =ExclusiveOr(C5,C4) everything is pretty straight forward. But in case it isn't here is what is happening (I'll explain the ExclusiveOr part below)

  

The decimal values in cells C4 and C5 are being converted into 16 bit binary values by the formulas in cells D4 and D5. Here is what the formula looks like for converting from decimal to 16 bit binary in Excel.

 

=DEC2BIN(INT(C4/256),8)&" "&DEC2BIN(MOD(C4,256),8)

  

What is happening above is the dec2bin() command is being used twice on the same cell C4. The first time it's converting the upper 8 bits of a number and the second time on the lower 8 bits of a number. The results are being 'stuck together' with a space between them by the &" "& in the formula.

  

The second interesting thing going on is counting the number of bits that are set to 1 after the conversion to binary. This is done in the cells E4 and E5 with the formula below.

 

=LEN(C5)-LEN(SUBSTITUTE(C5,"1",""))

What is happening here is the length function LEN() is first finding the length of the string in cell C5. In this case the length is 17 characters because there is a space between the first 8 numbers (first byte) and the second 8 numbers (second byte). Like this:

  

00000000 00100010 = 17 characters

 

The second thing that is happening is the SUBSTITUTE command is substituting "" which is nothing for all the 1's. After doing the substitution the second LEN() command is finding the length after all the 1's have been substituted with nothing "" or 'substituted away'. Like this:

  

00000000 00100010 = 17 characters

00000000 000000 = the above values with the 1's substituted with 'nothing'

00000000 000000 = 15 characters

17 - 15 = 2 so two 1's were removed.

What this all amounts to is you have the length before substitution of 17 being subtracted from the length after the 1's have been removed and that leaves you with the difference which is how many 1's have been taken away. Crazy isn't it? Anyway on to the first chart...

 

Bytes sorted by the number of bits set to 1

Anyway the reason that I am explaining all this is because it was important to making the above chart that shows all the bytes in decimal values sorted by the number of bits that are set to 1. Wow!!! Exciting! Near the upper left corner (click on it for a bigger view) of that picture in cells C3, C4 and C5 are what I just explained above. In C4 there is a number in decimal. If cells C4 there is that number converted to binary (16 bits but I only really need 8). And cell C5 is counting the number of 1's in cell C4. That big blue column on the left is the first prime numbers below 255. I added that just for fun to highlight the prime numbers in the chart.

  

What I did next was write a Visual Basic script that would set the value in cell C3 from 0 to 255. Each time it set the value the script would look at cell C5 to get the number of 1's that cell C3 had after being converted to binary by cell C4. Once the script knew how many 1's there were it copied that value into the chart in the appropriate column. I put the Visual Basic code at the bottom of this post if you are interested. Without wasting any more time below is what all that chart looks like!!!

  

The numbers in green are the total number of values in each column. The numbers in red are the number of bits set to 1. The numbers below are the values in decimal that have their bits set to 1 in the corresponding column. For example there are 23 values that have 2 bits set to 1, in that column they are 3, 5, 6, 9, (decimal) etc...

1	8	23	51	65	51	23	8	1
0	1	2	3	4	5	6	7	8
0	1	3	7	15	31	63	127	255
	2	5	11	23	47	95	191
	4	6	13	27	55	111	223
	8	9	14	29	59	119	239
	16	10	19	30	61	123	247
	32	12	21	39	62	125	251
	64	17	22	43	79	126	253
	128	18	25	45	87	159	254
		20	26	46	91	175
		24	28	51	93	183
		33	35	53	94	187
		34	37	54	103	189
		36	38	57	107	190
		40	41	58	109	207
		48	42	60	110	215
		65	44	71	115	219
		66	49	75	117	221
		68	50	77	118	222
		72	52	78	121	231
		80	56	83	122	235
		96	67	85	124	237
		129	69	86	143	238
		130	70	89	151	243
		132	73	90	155	245
		136	74	92	157	246
		144	76	99	158	249
		160	81	101	167	250
		192	82	102	171	252
			84	105	173
			88	106	174
			97	108	179
			98	113	181
			100	114	182
			104	116	185
			112	120	186
			131	135	188
			133	139	199
			134	141	203
			137	142	205
			138	147	206
			140	149	211
			145	150	213
			146	153	214
			148	154	217
			152	156	218
			161	163	220
			162	165	227
			164	166	229
			168	169	230
			176	170	233
			193	172	234
			194	177	236
			196	178	241
			200	180	242
			208	184	244
			224	195	248
				197
				198
				201
				202
				204
				209
				210
				212
				216
				225
				226
				228
				232
				240

Thrilling I know but the fun doesn't stop there!

  

After doing that I couldn't bring myself to stop it was so much fun and I decided to write another Visual Basic script that would list all the numbers that were different from a 'test number' by a certain number of bits. That last sentence is confusing so let me pit another picture in here.

 

Byte values that are different by 1 bit from all numbers in Excel

What is going on here is similar in some ways to what I explained above.  Let me start by explaining the picture. In column 'E' that says "Test Num" at the top are a bunch of decimal values. To the right in each corresponding row are the decimal values of the numbers that differ from the 'Test Num" by one bit. So for the first 'Test Num' of 0 the values 1, 2, 4, 8, 16 etc... differ from 0 by one bit. Can you believe it?!?! Again just for the hell of it I highlighted all the prime numbers in blue.

To do this I wrote a Visual Basic script that sets the value of cell C4 to 0 through 255. For each of the values in cell C4 the script sets the value in cell C3 from 0 to 255. Then the spreadsheet performs a logical Exclusive Or of those two cells using a custom function I wrote:

  

Function ExclusiveOr(A As Long, B As Long) 

ExclusiveOr = A Xor B

End Function 

  

The results of an Exclusive Or give you 1's everywhere bits are different in a pair of values. The Function above is pretty straight forward creating 2 variables A and B as data types Long. Then the function returns the Exclusive Or of those values with the Visual Basic Xor. Oh Yeah!

  

Once the Exclusive Or is calculated the script then puts that number in the row next to the 'test num' if the Exclusive Or result is equal to the value in cell C1. By changing that value and re-running the script I can make a chart that shows differences of any number of bits I want. To see the results of a few choice values go to this pre-dated post where I put all the results of this Excel insanity!!

  

One last thing I should mention about the above picture is the Excel "FALSE" value in cell C6. That is a booboo that I made before I took the screen shot and was fixed some time later... Send me an email at ottobelden@yahoo.com or leave a comment if you have any questions or see something wrong.

 

MS Excel Visual Basic Code:

The first block of code is what I wrote to sort the bytes by the number of bits that are set to 1.

Sub BitSort_1()
' This code will sort numbers based
'  on how many bits are set to 1
'  in each number then highlight
'  which numbers are prime
'
' http://ottobelden.blogspot.com/
' October 2010
'
Dim PrimeRow As Integer
Dim PrimeCol As Integer
PrimeRow = 2                ' top of prime
PrimeCol = 1
Dim TempCol As Integer
Dim TempRow As Integer
'
' Set Row Counters to 3
For SetRow = 0 To 16
    Cells(1, (SetRow + 5)) = 3
Next SetRow
'
For Number = 0 To 255
    Cells(3, 3) = Number    ' set num to test
    TempCol = Cells(5, 3) + 5 ' get column
    TempRow = Cells(1, TempCol) ' get offset
        Sheets("1000_Primes_Raw").Select
        If Cells(2, 11) = Cells(PrimeRow, PrimeCol) Then
            Sheets("65536 Primes").Select ' grab fill color
            Cells(1, 1).Copy
            Cells(TempRow, TempCol) = Cells(3, 3)
            Cells(TempRow, TempCol).PasteSpecial xlFormats
            PrimeRow = PrimeRow + 1
            Sheets("1000_Primes_Raw").Select
        Else
            Sheets("1000_Primes_Raw").Select
            Cells(TempRow, TempCol) = Cells(3, 3) ' place number
        End If
    Cells(1, TempCol) = Cells(1, TempCol) + 1 'increment row count
Next Number
End Sub

This is the code that I wrote to generate the lists of bytes that have a specific number of bit differences. Check out the picture and text above for how the sheet needs to be set up for this to work.

Sub BitsDiff()
' This code will sort numbers based
'  on how many bits are different
'  in each number from a test number
'  then highlight which numbers are prime
' The number of bits diff to test for
'  is in cell C1
' The Number to test against is in
'  cell C4
' http://ottobelden.blogspot.com/
' October 2010
'
Dim OutputCol As Integer
OutputCol = 6   'Starting column for output
Dim PrimeYes As Integer
PrimeYes = 0
Dim PrimeChk As Integer
PrimeChk = 2
'
Application.ScreenUpdating = False
For TestRow = 2 To 257
    Cells(4, 3) = Cells(TestRow, 5) ' set num to test
    For Test = 0 To 255 ' run thru num's to test
        Cells(3, 3) = Test
        If Cells(PrimeChk, 1) = Test Then
            PrimeYes = 1 'The number tested is a prime
            PrimeChk = PrimeChkPrimeChk = PrimeChk + 1
        End If
        If Cells(7, 3) = Cells(1, 3) Then ' right num of bits
            If PrimeYes = 1 Then
                Cells(1, 1).Copy
                Cells(TestRow, OutputCol).PasteSpecial xlFormats
            End If
            Cells(TestRow, OutputCol) = Test
            OutputCol = OutputCol + 1
        End If
    PrimeYes = 0
    Next Test
    OutputCol = 6   ' reset output col for next number
    PrimeChk = 2    ' reset prime checking to top of col
Next TestRow
Application.ScreenUpdating = True
End Sub