6. Bitwise Operations and Bitfields

We need tools to modify the bits themselves, this is what bitwise operations do.

Not

The simplest is the not operation or $\sim A$:

$A$	$\sim A$
0	1
1	0

When applying a not to a bunch of operations, teach each bit like a seperate operation, this goes for other bitwise operations!

$\underline{\sim\space 00111010}$
$= \space 11000101$

And

And is also simple, represented with $A\& B$:

$A$	$B$	$A \& B$
0	0	0
0	1	0
1	0	0
1	1	1

Properties

$x\& 0=0$, Basically forces a bit to be zero

$x\& 1=x$, Remains unchanged

Or

Also simple. $A | B$:

$A$	$B$	$A | B$
0	0	0
0	1	1
1	0	1
1	1	1

Properties

$x | 1=1$, Basically forces a bit to be one

$x | 0=x$, Remains unchanged

Xor

Now xor is a little different, this or means either one or the other, and not both ($A\verb!^! B$):

$A$	$B$	$A \verb!^! B$
0	0	0
0	1	1
1	0	1
1	1	0

Properties

$1 \verb!^! 0=0\verb!^! 1=1$, Is different

$1\verb!^! 1=0 \verb!^! 0=0$, Is not different

$x\verb!^! 0 = x$, Doesn't change

$x\verb!^! 1 = \sim x$, Flip

Bit shifting

What about shifting bits? Well we can do that!

We use sll reg1, reg2, [how far the shift] for a left shift ($B = A << 4$). The extra shifted bits will just go away. We can also right shift as well with srl.

This produces some interesting properties, for example, if we left shift by one, we actually double the value. So what we are really doing is $a<>n=\frac{a}{2^n}$ (massive issues do arise with signed numbers). To fixed said issue, we have sra which is shift right arithmetic.

With bit shifting, we can do some cool stuff:

• set(k, p) => $k = k | (1 << p)$, sets to 1 at position p.
• set(k, m, p) => $k | (((1 << m) - 1) << p)$, sets m bits to 1, or m+p-1 to p bits to 1.
• flip(k, p) => $k = k \verb!^! (1 << p)$
• reset(k, p) => $k = k \& (\sim (1 << p))$, sets to 0 at position p.

MIPS Commands

Instruction	Meaning
not a, b	$a = \sim b$
or a, b, c	$a = b|c$
ori a, b, imm	$a = b|imm$
and a, b, c	$a = b\&c$
andi a, b, imm	$a = b\&imm$
sll a, b, imm	$a = b<<imm$
sllv a, b, c	$a = b<<c$
srl a, b, imm	$a = b>>imm$ (zero extension)
srlv a, b, c	$a = b>>c$ (zero extension)
sra a, b, imm	$a = b>>imm$ (sign extension)
srav a, b, c	$a = b>>c$ (sign extension)

Bitfields

Sometimes we want one word to represent many different values, thankfully, we can use shifting and bit manipluation to achieve this. Why? Smaller data is better data, less space in memory, less space in cache, faster operations, etc.

Let's take RGB565 as an example:

We have three fields: red, green, blue.

Assembling this bitfield:

color = (red << 11) | (green << 5) | (blue << 0); 

Now, let's get the values back:

red = (color >> 11) & 0x1F;
green = (color >> 5) & 0x3F;
blue = color & 0x1F;

Wait, what are those hexadecimal numbers? Well they are masks, or a whole bunch of ones to get the bits we actually want, a table of them is below.

size(n)	mask	mask in hexadecimal	$2^n$	mask in decimal
1	$1_2$	0x1	2
2	$11_2$	0x3	4
3	$111_2$	0x7	8	7 = $2^n-1$ (too lazy to convert all of them)
4	$1111_2$	0xF	you get the idea
5	$11111_2$	0x1F
6	$111111_2$	0x3F
7	$1111111_2$	0x7F
8	$11111111_2$	0xFF
9	$111111111_2$	0x1FF
10	$1111111111_2$	0x3FF
11	$11111111111_2$	0x7FF
12	$111111111111_2$	0xFFF
13	$1111111111111_2$	0x1FFF
14	$11111111111111_2$	0x3FFF

In MIPS, instructions are represented in 32 byte bitfields.

And some Java code to grab/set each of the values

// Set
int opcode = 0x000008;
int rs = 0x00000;
int rt = 0x00010;
int imm = 0x0000000000001234;
int instruction = 0x0;
instruction = instruction | (opcode << 26);
instruction = instruction | (rs << 21);
instruction = instruction | (rt << 16);
instruction = instruction | (imm << 0);
System.out.printf("instruction: 0x%08X\n", instruction);

// Get
int ins = 0x20101234;
System.out.printf("opcode: 0x%02X\n", (ins >> 26) & 0x3F);
System.out.printf("rs: 0x%02X\n", (ins >> 21) & (0x1F));
System.out.printf("rt: 0x%02X\n", (ins >> 16) & (0x1F));
System.out.printf("imm: 0x%04X\n", (ins >> 0) & (0xFFFF));

Next Page →