Bit Hacking https://medium.com/learning-the-go-programming-language/bit-hacking-with-go-e0acee258827


(Cherolyn Lexvold) #21

I’m reading this on my phone presently. I can’t wait to get on the website so I can save all the good information you have given me


(Holloway) #22

There is no extra 1, but the most significant bit as the “negative/positive” sign flag. If you observe the example:

0b11111111 == -127
...
0b10000011 == -3
0b10000010 == -2
0b10000001 == -1
0b10000000 == -0
0b00000000 == 0
0b00000001 == 1
0b00000010 == 2
0b00000011 == 3
...
0b01111111 == 127

whereas unsigned is:

0b00000000 == 0
0b00000001 == 1
0b00000010 == 2
0b00000011 == 3
...
0b11111111 == 255

(Holloway) #23

@cherilexvold1974, do you need more clarifications? If the problem is solved, please help us “mark as solved”.


(Cherolyn Lexvold) #24

Not totally,but thanks for the comment because it brought me back here. I definitely need to study this further.

My main purpose in beginning this topic is to get answers to any questions I have about the article on Bithacking, which I have not finished reading. So thank you for bringing me back here. I will write a note to come back here the next time I study, hopefully tomorrow, since I have already run over my allotted time today :cry:


(Cherolyn Lexvold) #25

Studying &= and https://golang.org/ref/spec#Assignments and https://golang.org/ref/spec#Arithmetic_operators
and https://en.wikipedia.org/wiki/Bitwise_operation


(Holloway) #26

I think I missed out the 2 complement part.


Math Operations Problem (2-Compliment)

Now, if you follow the current signed number system, you will bump into mathematical operations problem. Take example:

# decimal
15 + (-5)
= 15 - 5
= 10

# binary operations
0b00001111 + 0b10000101
= 0b10010100
= -20  (base 10)  # so wrong

So to overcome it, we need to make use of the overflow as @NobbZ explained to represent negative numbers instead. Overflow means: 0b11111111 + 0b00000001 = 0b00000000. There’s where the 2 compliments comes in.

To interpret 1 in both signs
+1 == 0b00000001

For -1, you do 2 "stages" compliment by NOT-ing the positive value then add 1:
NOT 0b00000001 (1st stage)
--------------
    0b11111110
+   0b00000001 (2nd stage)
--------------
    0b11111111 (represent -1)
--------------

This way, when we do math operations in binary, we can have an agreeable mathematical operations.

# decimal
1 + (-1)
= 1 - 1
= 0

# binary
0b00000001 + 0b11111111
= (1) 0b00000000
= 0b00000000
= 0 (base 10)

Hence, if we check back out original example again with 2-compliment representations:

# decimal
15 + (-5)
= 15 - 5
= 10

# binary operations
0b00001111 + 0b11111011
= (1) 0b00001010
= 10  (base 10)  # now it is working fine

Therefore, to make sure we can have a smooth math operations while indicating signed numbers, we 2-complement all negative numbers instead. This officially changes the number representations into:

-127   | 0b11111111 --> (NOT 0b01111111) + 1 = 0b10000000 + 1 = 0b10000001
...
-3     | 0b10000011 --> (NOT 0b00000011) + 1 = 0b11111100 + 1 = 0b11111101
-2     | 0b10000010 --> (NOT 0b00000010) + 1 = 0b11111101 + 1 = 0b11111110
-1     | 0b10000011 --> (NOT 0b00000001) + 1 = 0b11111110 + 1 = 0b11111111
-128   | 0b10000000 --> (NOT 0b10000000) + 1 = 0b01111111 + 1 = 0b10000000
0      | 0b00000000
1      | 0b00000001
2      | 0b00000010
3      | 0b00000011
...
127    | 0b01111111

That’s why in signed integer, you get extra 1 element (e.g. 8-bit has [-128, 127]) on the negative side.


(Cory Galyna) #27

@hollowaykeanho, did you just shorten a 1.5 hours lectures into a single post? :sweat:

Give @cherilexvold1974 a break. :rofl:


(Cherolyn Lexvold) #28

This chart is very helpful.

Studying this example led me to a review of binary addition. I am confounded by
1111 + 0101. Don’t laugh, computer whizzez. :wink: I haven’t studied this since grade school. I don’t need simply the answer, but an explanation of the process, if you might be so humble.

Out of time, darn.


(Cory Galyna) #29

In number base system, base number represents the max numbers to overflow. Example:

// Base 10
    1
+   9
------
   10   // becomes 2 digits
------

// Base 8
   1
+  7
-----
  10  // becomes 2 digits
-----

// Base 5
   1
+  4
-----
  10  // becomes 2 digits
-----

// Base 2
   1
+  1
-----
  10 // becomes 2 digits
-----

So, when given 0b00001111 + 0b10000101, on base2, you overflow the addition when it hits 2:

+     1111  // overflow
 0b00001111 // 0b- represent base2, with value: 00001111
+0b10000101
-----------
 0b10010100
-----------

This works for all base numbers, as long as you hits the base numbers (max digits to overflow) like:

  1. base5 is 5
  2. base7 is 7
  3. base8 (octet) is 8
  4. base10 (decimal) is 10
  5. base16 (hexadecimal) is 16
  6. base256 (Duocentehexaquinquagesimal) is 256 or 2 hexadecimal or 1 byte (e.g. 0xFF)

Similarly, for subtraction, the maximum amount of borrow is the base number. E.g:

-  1111 1   // borrow from
+   2222 2  // borrow to
 0b10000101
-0b00001011
-----------
 0b01111010
-----------

We rarely do division or multiplication in other base numbers as they are very complex to comprehend for a lot of people. For those, there are 2 choices:

  1. Master your base number system comprehension (e.g. https://www.basic-mathematics.com/multiplication-in-base-two.html)
  2. convert back to base10, operate, then convert back to its base number.

(Cory Galyna) #30

Be careful. As he mentioned in the 2-Complement part:

The correct negative numbers representations should be the 2-Complement version, as in:


(Holloway) #31

@cherilexvold1974, @cory had nailed it for you. Do you have furthermore doubt or question about bit manipulations?


(Cherolyn Lexvold) #32

The 3rd column is what baffles me. I need this cleared up and then I can study the rest of the replies of the two of you.


(Holloway) #33

It’s like 99 + 1 for our ordinary numbers (which is base10). When the first column hits the base number 10, you overflow to the next column by 1. Then, on second column, 9 adds the overflow 1 is 10 again, overflow to another one, getting 100 in the end.

+ 11    // overflow
   99
+   1
-----
  100
-----

So what happens say 99 + 11? It’s the same case for first column. For second column, we now got 9+2 instead, giving 11. So what we do is to overflow to third column the # of times we subtract 11 with base number 10. Here, 11 - 10 = 1 (overflow: 1). The remainder stays at the second column.

+ 11    // overflow
   99
+  11
-----
  110
-----

The only difference here now is that instead of 10, on Base2, you overflow 1 when you hit 2.


(Cherolyn Lexvold) #34

Thanks!!!
I sort of knew that but I was unsure! Thanks for nailing it down!
Day off today, so I’m going to do a programming binge!

This makes me laugh :sweat_smile:

Now I don’t get the fifth column.

Thank God! Maybe some day when I’m really smart!


(Cory Galyna) #35

Similar to addition, for 100 to subtract 11, you borrow from the higher column when the focused one has insufficient to perform a subtraction.

-  1  1         // borrow
+    10 10      // borrow
   1  0  0
-     1  1
----------
      8  9
----------

As you borrow, you do 2 parts of math:

  1. You subtract the next higher column (2nd column) by 1.
  2. You add 10 to the focused column (1st column)

Since the first column’s balance is 0. It is insufficient so it borrows from the 2nd column. However, 2nd column also has 0 balance, so it borrows from 3rd column. Hence, we have subtraction of 1 borrow for both 2nd and 3rd columns respectively.

After borrowing, 2nd column gained maximum base value, which is 10 as balance. It then lends to the 1st column, where it also gained maximum base value (10) as balance. Now that we have enough balance for 1st column, we can do the subtraction and get 9.

Moving on to second column, since it has 10 balance, it now needs to subtract the loan for 1st column and its math. Hence, it becomes 10 - 1 (math) - 1 (loan), resulting 8 as balance. Lastly, the 3rd column has to do the same for subtracting loan balance, it which it resulted in 0.

That’s how you got 100 - 11 = 89 in base10 number system.


In base2, the maximum value is 2. Hence, instead of gaining 10 as balance, you get 2 as maximum balance per loan.

- 1 1 1 1   1      // borrow
+   2 2 2 2   2    // borrow
  1 0 0 0 0 1 0 1
- 0 0 0 0 1 0 1 1
-----------------
  0 1 1 1 1 0 1 0
-----------------

On 5th column, it gained 2 balance from its next higher column’s loan. However, itself is loaning to 4th column, resulting a borrow subtraction. Since it does not have any math subtraction, 2 - 1 (loan) = 1.


(Cory Galyna) #36

Just for extras.


Multiplication

It is straight forward addition by x-times. Example, on base10, it is:

152 * 6 = 152 + 152 + 152 + 152 + 152 + 152 = 912

Similarly, on base2, you do the same addition, n-times.

101 * 11 = 101 + 101 + 101 = 1111

Or you can use the conventional way:

        1 0 1
x         1 1
-------------
        1 0 1
+     1 0 1
-------------
      1 1 1 1
-------------

You just need to remember that on addition section, once you hit more than the maximum balance (indicated by base number), you increase the next higher column by x-times it overflows. On base2, that means:

  1. increase by 1 when hitting 2
  2. increase by 2 when hitting 4
  3. increase by 3 when hitting 6

Division

Division is actually the tricky part. You basically takes the dividend and subtract the divisor until you can’t subtract anymore (dividend (R‘) < divisor (D) OR dividend is 0). The remaining value is known as “remainder” (R) and the number of times you subtract is quotient (Q).

In other base number, there is no easy way to do divide like the conventional way we did aside doing such repeating and continuous subtraction.

Example, for base2 :

11101011 / 101
Q)  R‘       - D   = R
1)  11101011 - 101 = 11100110
2)  11100110 - 101 = 11100001
3)  11100001 - 101 = 01011100
...
46) 00001010 - 101 = 00000101
47) 00000101 - 101 = 00000000 // stop since R is less than D, which is equal to 0
----
Quotient (Q)   = 47 (base10) =  00101111 (base2)
Remainder (R)  =                00000000

WHY?

Remember you memorize multiplication table in school? Those efforts are only meant for base10.
To do that for every base number, you need to per-calculate the table again, memorize them again.

Reason for why divide by 0 is an error, not infinity
Try to do this division by subtraction for 1 / 0. You will realize it takes forever to calculate Q and R
and never gets a result at all.

Infinity by definition means so big that we can’t even count. It’s just too big.

Therefore, unable to calculate result simply does not mean “result is so big”.


(Holloway) #37

@cherilexvold1974, @cory nailed it again.

@cory, why?! why did you brought in multiply and divide?! You’re going to send her to lala-land soon. :rofl:


(Cherolyn Lexvold) #38

Lol thanks sincerely for the review. Gosh it’s been a long time since I did that. I rely so much on calculators that I forgot simple math!

Hence, I also get what you said about subtracting in base 2