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
Bit Hacking https://medium.com/learningthegoprogramminglanguage/bithackingwithgoe0acee258827
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
@cherilexvold1974, do you need more clarifications? If the problem is solved, please help us “mark as solved”.
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
Studying &= and https://golang.org/ref/spec#Assignments and https://golang.org/ref/spec#Arithmetic_operators
and https://en.wikipedia.org/wiki/Bitwise_operation
I think I missed out the 2 complement part.
Math Operations Problem (2Compliment)
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 NOTing 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 2compliment 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 2complement 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. 8bit has [128, 127]
) on the negative side.
@hollowaykeanho, did you just shorten a 1.5 hours lectures into a single post?
Give @cherilexvold1974 a break.
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. 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.
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:

base5
is5

base7
is7

base8
(octet) is8

base10
(decimal) is10

base16
(hexadecimal) is16

base256
(Duocentehexaquinquagesimal) is256
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:
 Master your base number system comprehension (e.g. https://www.basicmathematics.com/multiplicationinbasetwo.html)
 convert back to
base10
, operate, then convert back to its base number.
Be careful. As he mentioned in the 2Complement part:
The correct negative numbers representations should be the 2Complement version, as in:
@cherilexvold1974, @cory had nailed it for you. Do you have furthermore doubt or question about bit manipulations?
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.
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
.
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
Now I don’t get the fifth column.
Thank God! Maybe some day when I’m really smart!
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:
 You subtract the next higher column (2nd column) by
1
.  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
.
Just for extras.
Multiplication
It is straight forward addition by xtimes. Example, on base10
, it is:
152 * 6 = 152 + 152 + 152 + 152 + 152 + 152 = 912
Similarly, on base2
, you do the same addition, ntimes.
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 xtimes it overflows. On base2
, that means:
 increase by 1 when hitting 2
 increase by 2 when hitting 4
 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 percalculate the table again, memorize them again.
Reason for why divide by 0 is an error, not infinity
Try to do this division by subtraction for1 / 0
. You will realize it takes forever to calculateQ
andR
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”.
@cherilexvold1974, @cory nailed it again.
@cory, why?! why did you brought in multiply and divide?! You’re going to send her to lalaland soon.
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