Copy
View this email in your browser

In today’s newsletter, we’ll go through the basic operations that we need to be able to manipulate bytes so we can get to implementing one of my favorite data structures, the bitset.

This newsletter will be a little light on content because at the end, there will be a couple exercises for you to do that we’ll go over tomorrow that will set us up well for implementing a BitSet.

With that, let’s get started!
 

Bitwise operators

Bitwise operators are best explained through examples. For all of these examples, we’re going to be manipulating 16 bit integers.

Bitshift

The bitshift left & right operators let us shift bits left or right. For example:

110 = 0000 0000 0000 00012

Left Shift

0000 0000 0000 00012 << 1 == 00000000 000000102 == 210

Right Shift

0100 1111 0000 00002 >> 4 == 0000 0100 1111 00002

Note that the behavior is undefined if the number of bits to shift by exceeds the number of bits available:

In Java:

int f = 1 << 33;
System.out.println(f); // 2


The results depend on the language, but we typically don’t have a use case for shifting bits more than the type’s allotted size.

Bitwise And, Or, & XOR

Each of the following operations lines up the binary representation of two numbers bit by bit and performs an operation:

Bitwise And

Scans through the bits. If both bits are set to 1, returns 1 for that bit otherwise 0

00000000 00001010 & 00000000 00001000

00000000 00001010
00000000 00001000 &
-------------------
00000000 00001000



Bitwise Or

Scans through the bits. If either bit is set to 1, returns 1 for that bit, otherwise 0.

00000000 00001010 | 00000000 00001000

00000000 00001010
00000000 00001000 |
-------------------
00000000 00001010


Bitwise XOR

Scans through the bits. If exactly one bit is set to 1, returns 1 for that bit, otherwise 0.

00000000 00001010 ^ 00000000 00001000

00000000 00001010
00000000 00001000 ^
-------------------
00000000 00000010


Bitwise Not

Lastly, we have bitwise not. It’s applied to a single number and flips all the bits in its internal representation:

~(00000000 11111111) = 11111111 00000000

Let’s practice!

In preparation for tomorrow’s newsletter, let’s go ahead and practice using these operations!

Assume that we’re working with 32 bit integers for each of these problems.

  1. Write a method called zebra that returns an int with every other bit set to 1.
  2. Write a method that takes in an integer x and another int, n, and flips the nth bit. That is, if the nth bit in the binary representation of integer x is 0, set it to 1, otherwise set it to 0.
  3. A palindrome is defined as a sequence that reads the same backwards as forward. Write a function that takes in an integer and returns a boolean which denotes whether or not its binary representation is a palindrome. True if it’s a palindrome, false otherwise.

We’ll go over these problems in tomorrow’s newsletter. Happy solving!

As always, below is the Discord if you want to chat or give feedback :).



Justin

Copyright © 2021 Gestone, All rights reserved.


Want to change how you receive these emails?
You can update your preferences or unsubscribe from this list.

Email Marketing Powered by Mailchimp