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


(Cherolyn Lexvold) #1

func main() {
var x uint8 = 0xAC // x = 10101100
x &= 0xF0 // x = 10100000
}

What is uint8?
What is 0xAC?
10101100 …172?
What is &=?
What is 0xF0?
10100000…160?

Are AND and & the same?

https://play.golang.org/p/1OU2kehp5EW
Where did the numbers in the output come from?

Are | and OR the same?

What is MSB?

I don’t want to stop! But i must. Catch you later


(Sean Killian) #2

To answer your questions exactly:

uint8 is defined in the Go language specification here: https://golang.org/ref/spec#Numeric_types

0xAC is a hexadecimal numeric literal also defined in the language specification here: https://golang.org/ref/spec#Integer_literals

&= is an assignment operator that is defined in the spec. here: https://golang.org/ref/spec#Assignments

The single ampersand, &, performs a bit-wise AND of its operands and is defined under Arithmetic operators: https://golang.org/ref/spec#Arithmetic_operators

The bit-wise OR operator, | is defined in the same section.

That all being said, I recommend you check out some further reading in Wikipedia for some explanation: https://en.wikipedia.org/wiki/Bitwise_operation. I often use Wikipedia and YouTube to familiarize myself with new concepts because there are often diagrams to visually demonstrate what’s going on.

Finally, regarding your question about where the numbers are coming from in the example you posted, before I answer, can you clarify what part in the example is unclear to you?


(Cherolyn Lexvold) #3

Thanks for pointing me in the right direction! I followed the link and saved it to a file. I had read it before, but this time I understand better.

In hexadecimal literals, letters a-f and A-F represent values 10 through 15…Ohhhh. I was introduced to this awhile ago, but it is so new to me that I did not recognize it.

https://golang.org/ref/spec#Assignments This is pretty much Greek to me. My teacher taught that & is a pointer to an int which shows a memory address. My understanding is very basic. So I didn’t know what &= means.

The single ampersand, & , performs a bit-wise AND of its operands and is defined under Arithmetic operators: https://golang.org/ref/spec#Arithmetic_operators Starting to get this. New to the concept of bit-wise.

Thanks for the link to Arithmetic Operators. I actually was looking for this. I don’t know how I missed it.

Reading this: https://en.wikipedia.org/wiki/Bitwise_operation .
“On simple low-cost processors, typically, bitwise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition.” This is cool. No wonder people use it.
I will continue this tomorrow (hope, hope)

From the Wikipedia article…" A bitwise AND is a binary operation that takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, which is equivalent to multiplying them. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). For example:

010 1 (decimal 5) AND 001 1 (decimal 3) = 000 1 (decimal 1)"

How could 5 x 3 = 1?


(Norbert Melzer) #4

Its like multiplying them bitwise, as in the quoted example.


(Cherolyn Lexvold) #5

But what does that mean?

Please compare/contrast with the multiplication I learned in gradeschool, if possible


(Norbert Melzer) #6

You already quoted it from wikipedia.

You have 5 and 3, which in binary representation (4 bit) are 0101 and 0011.

Now you multiply the binary representation bit by bit (0 * 0 = 1, 1 * 0 = 0, 0 * 1 = 0 and 1 * 1 = 1). Then you put them back into a binary number, 0001 which in decimal is 1.


(Cherolyn Lexvold) #7

In reviewing your answer here, I went to this link.

I came to this statement. " The value of an n -bit integer is n bits wide and represented using two’s complement arithmetic."

I then followed this link: two’s complement arithmetic."

Which included this chart:

Three-bit signed integers Decimal
value Binary
(two’s-complement
representation) Two’s
complement
(23 − n )2
0 000 000
1 001 111
2 010 110
3 011 101
−4 100 100
−3 101 011
−2 110 010
−1 111 001

Kind of unclear here. You might want to go to the link.
I don’t understand the representation of the negative numbers, nor the two’s complement representation


(Lutz Horn) #8

This question is not specific to Go. It is a general question about bits, binary numbers and operations on them.


(Norbert Melzer) #9

“Twos complement” basically means negate every bit and then add 1.

The following will assume 3 bits again:

decimal -> binary representation -> negated all bits -> added one (which is the same as multiply by -1 decimal)
 0 -> 000 -> 111 -> 000
 1 -> 001 -> 110 -> 111
 2 -> 010 -> 101 -> 110
 3 -> 011 -> 100 -> 101
-4 -> 100 -> 011 -> 100 // warning! 4 is not representable in 3 bits signed!
-3 -> 101 -> 010 -> 011
-2 -> 110 -> 001 -> 010
-1 -> 111 -> 000 -> 001

The (2^m - n)_2 notation confuses a lot of people that do not have the mathematical background, and therefore hasn’t even been touched during the first semestre of my CS graduation, but only has been clanced over in the 3rd or 4th, even though 2s complement was introduced during the first as it is fundamental.

And it has been introduced in the two step fashion I explained it here. Its usually universally understandable who at least understands the basics of binary numbers and negating single bits.


(Cherolyn Lexvold) #10

Let me see if I understand you right .

Twos complement” basically means negate every bit and then add 1.

0->000->111

I will stop here. So in 000, you negate each 0 and add 1, and hence 111?

I don’t understand the fourth column.

I think I get the first three columns for 1

I don’t get the third car alarm for 2. Shouldn’t it be 011?

-4 -> 100 -> 011 -> 100 // warning! 4 is not representable in 3 bits signed!

Why is that ?

I don’t get the third column for -2 and -2

I’m sorry that my education is so lacking . There are reasons for that . I appreciate your patience .


(Cherolyn Lexvold) #11

Right. I’m currently studying it (on my own with limited time). Slow process


(Norbert Melzer) #12

“negating” a bit means making a 0 a 1 and vice versa, and you do this for each digit. So this has not yet todo anything with adding anything, its just the first of two steps to build the 2s complement. Only after all bits are flipped, you add 1, and adhere to carries.

No, I negate each 0 to a 1, such that I get 111, then I add 1, which results in 000 due to carry and overflow.

No, thats just adding one, without negating all bits first.

Because, as you can see from the table, 4 had the same representation as -4. Thats why in any signed representation -(MIN + 1) == MAX.

I think you mean -2 and 2?

What exactly do you not understand? Is it still because of your misconception of negating each bit? Or is it something else?


(Cherolyn Lexvold) #13

negating” a bit means making a

0 a 1 and vice versa, and you do this for each digit.

Thanks :pray: Very helpful.

No, I negate each 0 to a 1, such that I get 111, then I add 1, which results in 000 due to carry and overflow.

Got it :blush: cool.

I really enjoy it when I get understanding .

I went over the chart and I’m understanding it.

Because, as you can see from the table, 4 had the same representation as -4. Thats why in any signed representation -(MIN + 1) == MAX.

Don’t worry about the last question because what you said already answers that question.

For some reason I’m not getting this. I do see that four and -4 have the same representation. I know what assigned representation is . What is == MAX? Is there a way to differentiate 4 from -4 ?


(Norbert Melzer) #14

Only half of the equation.

I said -(MIN + 1) == MAX, which could be rewritten as MIN == -MAX - 1, which basically means, that for any signed integer the minimal representable value is equal to the negative of the maximum representable value minus one…

Well, if you have more than 3 bits signed, then you can represent 4 of course and therefore differentiate -4 from it easily. Lets consider 4 bits signed:

 4 -> 0100 -> 1011 -> 1100
-4 -> 1100 -> 0011 -> 0100

With 4 bits signed you can represent values from 7 to -8.


(Cherolyn Lexvold) #15

I said -(MIN + 1) == MAX, which could be rewritten as MIN == -MAX - 1, which basically means, that for any signed integer the minimal representable value is equal to the negative of the maximum representable value minus one…

Interesting. I’d be interested to hear more about “the minimal representable value “ and “the maximum representable value “

With 4 bits signed you can represent values from 7 to -8.

Interesting.


(Norbert Melzer) #16

What exactly?

The essence is, if you have a limited amount of digits, then you have only a limited amount of values representable. Its like with your car. You have 6 digits for your mileage, starting at 0, maximum value will be 999999. After that it will roll over to 0. Its similar with binary numbers. With the only exception that we only have 0 and 1 as digits, and not 0 to 9.

The next thing is, that we do not have a - to indicate negativity of a value. But instead some engineers agreed on making the most significant bit the “minus” in signed integer types. Also the agreed on using 2s complement rather than just inverting each bit because you can add negative and positive numbers directly in 2s complement:

Lets calc `-2 + 3` with 3 bit signed integers

dec    2s complement     plain invert
 -2    110               101
+ 3    011               011
===    ===               ===
  1 (1)001            (1)000

As you can see, in the 2s complement notation we naturaly see the binary representation of 1, while in the plain invert we’d need to keep track of the fact that we passed 0 boundary and had to manually add another 1 to correct the result.


(Holloway) #17

Regarding about your relation where -(MIN + 1) == MAX, you’re confused with with data type in binary nature. You can’t simply say a 129 (base10) is equal to -1 (base10) by just looking at the binary data, which in fact, they’re the same binary value: 0b10000001. To really look into this, you have to understand why do we still use bitwise operations in a very powerful computer today.

The Origin

The most native form of representation is always unsigned number, where you can say 0b1000001 is 129 (base10) or to me, switching on bit-8 and bit-1.

The reason is because bit-wise operation is heavily related to hardware interaction itself. To put it bluntly, each bit is mapped into the “switches” on hardware. Imagine each bit is like your house light switches, switching bit-8 and bit-1 to 1 is equivalent to pressing your 8th light switch and 1st light switch on.

Base-2 & Other Numbering System

In computer science, 8-bits “data” can also means number of 0 (0b00000000) to 255 (0b11111111) if we relate it mathematically. As you understand, 0b10000001 is base 2 while our number system 129 is base 10. By relating the bitwise “data”, you can easily convert base 2 number to any base numbers like base6 (hex), base8 (octet), and base10 (decimal).

Hence, computer is used for calculations, lots of lots of calculations.

The Signed Number?

As we all know, number system has negative numbers but the bitwise data does not support signed flag. The maximum binary value is 255 (base10) which is 0b11111111. After a long research, scientists decided to say “hey, let’s use the most significant bit (in our example, it is 0b10000000) as the sign flag”. That also means the effective numbers an 8-bit can represent is now left with 7-bits, giving the signed number a range:

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

compared to previous switches unsigned, which is:

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

Yet, we still need to maintain the original unsigned nature in order to control the computer (light switches does not understand math). That’s where scientists decided to define data types, unsigned and signed. The one you asked about uint8 is known as unsigned integer, 8-bit maximum which means 0b11111111 is 255, not -127. The signed version is int8.

This is why the early C language and Go language are particularly strict with data types. You need to know your data nature before computing the data. Otherwise, 0b11111111 could means anything.

Changing Bits?

With the data definition in place, we need to operate the numbers. So, we use logic gates (hardware) to runs the operations. There are AND, OR, XOR, XAND, and etc. to flip the hardware switches and it is exactly the same interpretation in software as well. The given Wikipedia explained the operations clearly so I will skip explaining each operations.

At hardware and unsigned data nature, back to our 0b10000001 example, to turn the bit-7 switch on, we OR the data with out intended value.

       0b10000001
OR     0b01000000
-----------------
       0b11000001
-----------------

If we want to check the status of the bit-7 switch, we AND the data with the intended value.

       0b11000001
AND    0b01000000
-----------------
       0b01000000
-----------------

You get the idea.

Can I operate with NOT?

Say, now you want to only turn on all but not bit-2 switch only, there are 2-ways to do it:

  1. You OR the value with 0b11111101
  2. You OR the complement value of bit-2 switch
        0b10000001
OR (NOT 0b00000010)
-------------------
        0b10000001
OR      0b11111101  (Simplified NOT 0b00000010)
-----------------
        0b11111101
-----------------

NOT or compliment simply means “the other side of values”. In bitwise, it means 1 if 0, 0 if 1. It makes sense since 0 is a compliment of 1 to be “binary” fulfilled (0 and 1) and vice versa.

With NOT, you can express the operation clearer, like “turn on all but not bit-2 switch” instead of “turn on bit 1,3,4,5,6,7,8”.

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 to the signed number representations becomes:

-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 [-128, 127] on the negative side.

Scaling The Size

Now that we understand how bitwise operations work, let’s scale it from 8-bit to 16-bit, this gives us the 8086 microprocessor, then let’s scale it to 32-bit, gives us ia32 processor, and to 64-bit, amd64 processor.

At each scaling, with all the bit switched on, the magnitude of data getting bigger. You get:

  1. 16-bit has 65535 (uint16), and [-32768, 32767] (int16)
  2. 32-bit has 4294967295 (uint32), and [-2147483648, 2147483647] (int32)

Tl; DR: each time you add a bit space, the total operational numbers scaled significantly.

Translate to Code

To visualize in code, instead of writing mathematical operations like the above, our code uses different representations. Back to our NOT example, the code simply means:

switches := uint8(0b10000001)
output := switches | (^uint8(0b00000010))
fmt.Printf("0b%b\n", output) 
# output: 0b11111101

Applying good coding practice, you get:

package main

import (
	"fmt"
)

const (
	switch1 = uint8(0b00000001)
	switch2 = uint8(0b00000010)
	switch8 = uint8(0b10000000)
)

func main() {
	switches := switch8 | switch1
	output := switches | (^switch2)
	fmt.Printf("0b%b\n", output)
}
// output: 0b11111101

When Do We Use Bitwise Operations

  1. Interfacing with hardware (e.g. light switches remember?). This is in the field of Internet of Things.
  2. Highly optimized flag registers. Some of us (like me) uses bitwise operations to build a flag registers, similar to multiple boolean cases under a single data type.
  3. High speed data processing (e.g. real-time signal processing) where parallel bits setting is required (e.g. filter).
  4. Cryptography cipher development

No. 1, 3, and 4 are the main and rational reasons to use bitwise operations. 2 is rarely needed. I barely use it in Go apart from killing time with curiosity.


Hope this clear things up.

p/s: by the way, is this your module assignment?


(Cherolyn Lexvold) #18

Interesting . What is the most significant bit?


(Holloway) #19

Now, try to comprehend this on your side and find which bit is responsible for flagging the sign.


(Cherolyn Lexvold) #20

Very interesting! Thanks for the education!

So is it the extra 1 that makes it negative?