Categories

Please confirm that you want to add **Guide To Hacking Bits in C#** to your Wishlist.

Helpful Techniques For Bit Manipulation in C# Coding Interviews

40 students enrolled

Created by
Ovni Software

Last updated 5/2016

English

Current price: $10
Original price: $20
Discount:
50% off

30-Day Money-Back Guarantee

- 3 hours on-demand video
- 1 Supplemental Resource
- Full lifetime access
- Access on mobile and TV

- Certificate of Completion

What Will I Learn?

- Be able to solve bit manipulation problems
- Know how to memorize truth tables
- Be able to convert integers to binary
- Be able to convert binary to integers

Requirements

- Download Visual Studio 2015
- Be familiar with C#

Description

Learn techniques to solve bit manipulation problems in C# using Visual Studio 2015. After taking this course you will be equipped to answer common bit manipulation coding interview questions.

**Master techniques to answer bit manipulation coding interviews questions**

- Learn primary bit manipulation techniques

- Learn fun trick to memorize truth tables

- Learn how to answer some of most common bit manipulation interview questions

- Learn how bit manipulation works specifically in C#

**A skill that will set you apart**

This course is aimed at those who are preparing for a coding interview and want to brush up on their bit manipulation skills. When interviewing for software development positions, a strong understanding of bit manipulation techniques may help you to stand out against other candidates.

**Content and Overview**

This course is meant for those who have some coding experience and are somewhat familiar with C# and have downloaded Visual Studio 2015. This course is not meant for absolute beginners in C#. Bit manipulation is explained in detail and the primary techniques used to manipulate bits are covered.

Who is the target audience?

- People who are preparing for a coding interview
- People interested in how binary works
- People interested in solving bit manipulation problems in C#
- People who have no coding experience should not take this course
- People who have no experience with C# should not take this course
- People who do not have Visual Studio 2015 installed on their machine should not take this course

Students Who Viewed This Course Also Viewed

Curriculum For This Course

44 Lectures

02:47:49
+
–

Course Overview
2 Lectures
05:01

It has been said that a warrior should not just possess a weapon, he or she must also know when and how to use it. This course will not only arm you with the proverbial programming weapons,but it will also show you when and how to use them to solve difficult bitwise manipulation questions.

Preview
02:31

Top tech companies such as Google, Facebook, Apple, Amazon, etc. ask bit manipulation questions when deciding who they want to hire as employees. Help yourself stand out against other candidates by being able to fully break down these types of problems and explain them to your interviewer in easy to understand terms.

A lot of tech companies expect candidates to answer these questions at a whiteboard.

Why Learn This? Which Companies Ask These Interview Questions?

02:30

+
–

Bitwise Basics
4 Lectures
13:40

All information on a hard drive is stored at it's lowest level as 1's and 0's. Example, the number 8 is stored as 1000.

Each digit in 1000 is referred to as a bit (so it's 4 bits).

When a datatype is referred to as 8 bit, it means it is made up of 8 digits like this: 1000 0000.

Preview
02:08

Bit manipulation is directly interacting with the digits that make up a binary number.

Most programmers do not work on a bit level on a regular basis and for good reason. It is generally easier to write and understand program using things that represent the binary digits instead of the binary digits themselves.

What Is Bit Manipulation?

01:53

Most of the time people use base 10. This is the numbering system based on the number ten. For example the number one hundred twenty three can be broken down like this:

Instead of 123, how about:

(10^0 * 3) = 3

(10^1 * 2) = 20

(10^2 * 3) = 100

Adding these numbers up we get 123.

Similarly in binary or base 2 the number 0111 can be thought of as:

(2^0 * 1) = 1

(2^1 * 1) = 2

(2^2 * 1) = 4

(2^3 * 0) = 0

Adding these numbers up we get 7

Binary (Base 2) vs Decimal (Base 10) Numbering Systems

04:42

.101 (binary) is converted to a fraction with this method:

(1/(2^0) * 1) = .5

(1/(2^1) * 0) = 0

(1/(2^2) * 1) = .125

Adding these numbers up we get .625 or 5/8.

More examples:

.01 = .25

.1 = .5

.11 = .75

How Are Fractions Stored In Binary?

04:57

+
–

Foundational Techniques
11 Lectures
38:24

We will use these 4 operators to perform calculations on binary numbers.

The stronger grasp you have of how these operators work, the easier it

will be to understand how and when to apply them.

The 4 gates diagram is known as a truth table. The first two columns represent inputs and the last column represents the result.

Preview
05:00

//| (Or), this is the vertical bar on the keyboard, sometimes called a pipe

//0101(5) Input

//0111(7) Input

//0111(7) Result

int y = 5 | 7;

Console.WriteLine(y);

Console.WriteLine("Binary: " + Convert.ToString(y, 2).PadLeft(29, '0'));

Or Operator |

04:17

//^ (Exclusive OR, also known as XOR)

//0101(5) Input

//0111(7) Input

//0010) (4) Result

int z = 5 ^ 7;

Console.WriteLine(z);

Console.WriteLine("Binary: " + Convert.ToString(z, 2));

XOR Operator ^

02:41

//~(Not, also known as ones complement operator)

//5 0101

//10 1010

int x = ~5;

Console.WriteLine(x);

Console.WriteLine("Binary: " + Convert.ToString(x,2));

Anytime in C# that you use the ~ against an integer it will change the integer's

parity, negative will become positive and positive will become negative.

This is because the 32nd bit is always set/turned on for negative

numbers. The 32nd bit is always not set/turned off for positive

numbers.

Not Operator ~

04:04

//Shifts one digit to the right

//So 0100 (4) becomes 0010 (2)

int x = 4 >> 1;

Console.WriteLine(x);

Console.WriteLine("Binary: " + Convert.ToString(x, 2));

//Shifts one digit to the left

//0100 (4) becomes 1000 (8)

int y = 4 << 1;

Console.WriteLine(y);

Console.WriteLine("Binary: " + Convert.ToString(y, 2));

//Can also shift by multiple positions

//1000 (8) becomes 0010

int z = 8 >> 2;

Console.WriteLine(z);

Console.WriteLine("Binary: " + Convert.ToString(z, 2));

Explain shifting bits to left and right

Shifting 1 digit to the right divides by 2

Shifting 1 digit to the left multiplies by 2

To help remember this, you can use the acronym DR. Martin Luther.

Divide Right, Multiply Left

Bit Shifting (Right and Left)

03:10

Technique to remember how to write out the truth table

How To Remember The Truth Tables

02:11

//Converts integer 8 to binary equivalent of "1000"

string binaryString = Convert.ToString(8, 2);

Console.WriteLine(binaryString);

//Converts binary "1000" to integer 8

int x = Convert.ToInt32("1000", 2);

Console.WriteLine(x);

Solving bit manipulation problems using string manipulation is used as a last resort in solving these problems because it is technically not a bitwise operation

If
you can't figure out how to solve a problem using the other techniques,
it is generally easier to solve using string manipulation

Note
that this method is frowned upon and can be seen as taking the easy way
out, but if you have tried using the other techniques and are really
stumped, it may be better to go with this. At least you may come up
with a working solution which is better than nothing.

String Manipulation

05:02

//7 0111

//8 1000

int x = 8;

if ((x & 1) != 0)

Console.WriteLine("Number is odd");

else

Console.WriteLine("Number is even");

Can be used to determine if int is odd or even

if ((x & 1) != 0) //Returns true for 3 (11)

Testing If The Last Bit Is Set

03:52

//1000 (8)

//By turning on the last bit we add one to it

//1001 (9)

int x = 8;

x = x | 1;

Console.WriteLine(x);

//0111 (7)

//By turning on the last bit we add one to it

//0111 (9)

int y = 7;

y = y | 1;

Console.WriteLine(y);

Turning
on the last bit means making sure the farthest right bit is set equal
to 1. In the case of 8, setting the last bit will change the value to
1. In the case of 7, since the last bit is already set, this operation
will have no effect and we will still get 7.

Turning On The Last Bit

02:58

//1000 (8)

//By turning off the last bit we subtract one from it (if it's odd, if it's even it has no effect)

//1000 (8)

int x = 8;

x = x & ~1;

Console.WriteLine(x);

//0111 (7)

//By turning off the last bit we subract one from it (if it's odd, if it's even it has no effect)

//0110 (6)

int y = 7;

y = y & ~1;

Console.WriteLine(y);

Turning
off the last bit means making sure the farthest right bit is set equal
to 0. In the case of 8, turning off the last bit will have no effect
and we will still get 8. In the case of 7, since the last bit is turned
off, turning it on will have the effect of subtracting one and we will
get 6.

Turning Off The Last Bit

02:24

//1000 (8)

//By toggling the last bit, in this case, we turn it on since it was turned off which has the effect of adding one.

//1001 (9)

int x = 8;

x = x ^ 1;

Console.WriteLine(x);

//0111 (7)

//By toggling the last bit, in this case, we turn it off since it was turned on which has the effect of subtracting one.

//0110 (6)

int y = 7;

y = y ^ 1;

Console.WriteLine(y);

Toggling
the last bit means setting it equal to 1 if it was 0 (has effect of
adding one). Or setting it equal to 0 if it was 1 (has effect of
subtracting one).

Toggling The Last Bit

02:45

+
–

Working With The nth Bit Techniques
6 Lectures
22:24

//0111 (7)

//Testing which bits are set

int y = 7;

Console.WriteLine("7 in binary is: " + Convert.ToString(7,2));

if ((y & (1 << 0)) != 0)

Console.WriteLine("0th bit is set");

if ((y & (1 << 1)) != 0)

Console.WriteLine("1st bit is set");

if ((y & (1 << 2)) != 0)

Console.WriteLine("2nd bit is set");

if ((y & (1 << 3)) != 0)

Console.WriteLine("3rd bit is set");

Material:Testing if the nth bit is set combines the Checking if last bit is set technique and the left shift

11111110 (1 << 0)

11111101 (1 << 1)

11111011 (1 << 2)

11110111 (1 << 3)

11101111 (1 << 4)

11011111 (1 << 5)

10111111 (1 << 6)

01111111 (1 << 7)

Preview
05:20

//Testing for positive or negative by shifting 31 positions left

//7 0111

int y = 7;

int z = -7;

Console.WriteLine("-7 in binary is: " + Convert.ToString(z,2));

if ((y & (1 << 31)) != 0)

Console.WriteLine("7 is negative");

if ((z & (1 << 31)) != 0)

Console.WriteLine("-7 is negative");

Testing If The Farthest Left Bit Is Set

03:02

//1000 (8)

//This will turn off the third bit and we will get 0

//0000 (0)

int x = 8;

Console.WriteLine("8 in binary is: " + Convert.ToString(x, 2));

x = (x & ~(1 << 3));

Console.WriteLine("Result is : " + Convert.ToString(x,2));

This combines turning off the last bit and left-shift

Turning Off The nth Bit

03:41

//1000 (8)

//This will turn on the second bit and we will get 12

//1100 (12)

int x = 8;

Console.WriteLine("8 in binary is: " + Convert.ToString(x, 2));

x = (x | (1 << 2));

Console.WriteLine("Result is : " + Convert.ToString(x,2));

This combines setting the last bit and left-shift

Turning On The nth Bit

03:29

Show how to turn off bits in a range

//15 1111

int x = 15;

Console.WriteLine("15 in binary is: " + Convert.ToString(x,2));

for (int i = 1; i < 3; i++)

{

x = x & ~(1 << i);

}

//x = (x & ~(1 << 3));

Console.WriteLine("Result is:" + Convert.ToString(x,2));

Turn Off Bits In a Range

03:16

Combines toggling last bit and left-shift

//1000 (8)

//This will toggle the first bit and we will get 10

//1010 (10)

int x = 8;

Console.WriteLine(x + " in binary is: " + Convert.ToString(x, 2));

x = (x ^ (1 << 1));

Console.WriteLine("Result in binary is : " + Convert.ToString(x,2));

Console.WriteLine("Result in decimal is: " + x);

Toggling The nth Bit

03:36

+
–

Working With The RightMost Bit Techniques
5 Lectures
21:19

Rightmost set bit becomes a 0

//10 1010

//9 1001

//8 1000

//int x = 10;

//x = x & (x-1);

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine(Convert.ToString(-x, 2).PadLeft(32, '0'));

x = x & (-x);

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Can be used to determine whether an integer is a power of 2

//8 1000

//7 0111

// 0000

int y = 8;

y = y & (y - 1);

if ((y & (y - 1)) == 0)

Console.WriteLine("y is a power of 2");

Turning Off Rightmost 1-Bit

06:14

Finds the rightmost 1-bit and sets all the other bits to 0. The end result has only that one rightmost 1-bit set.

int x = 15;

//x = x & (-x);

Console.WriteLine("answer in binary is " + Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine("answer in binary is " + Convert.ToString(-x, 2).PadLeft(32, '0'));

//10 0000 1010

int x = 10;

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine(Convert.ToString(-x, 2).PadLeft(32, '0'));

x = x & (-x);

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Isolating The Rightmost 1-Bit

04:32

All the 0-bits right to the rightmost 1-bit got turned into ones.

//16 0001 0000

// 0000 1111

// 0001 1111

int x = 16;

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine(Convert.ToString(x-1, 2).PadLeft(32, '0'));

x = x | (x - 1);

Console.WriteLine(Convert.ToString(x, 2).PadLeft(32, '0'));

Right Propagating The Rightmost 1-Bit

04:27

Finds the rightmost 0-bit, turns off all bits, and sets this bit to 1 in the result

int x = 9;

Console.WriteLine(x + " is " + Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine("~" + x + " is " + Convert.ToString(~x, 2).PadLeft(32, '0'));

Console.WriteLine(x + " plus one is " + Convert.ToString(x + 1, 2).PadLeft(32, '0'));

x = ~x & (x + 1);

Console.WriteLine("Result is: " + Convert.ToString(x, 2).PadLeft(32, '0'));

int x = 8;

Console.WriteLine(x + " is " + Convert.ToString(x, 2).PadLeft(32, '0'));

Console.WriteLine("~" + x + " is " + Convert.ToString(~x, 2).PadLeft(32, '0'));

Console.WriteLine(x + " plus one is " + Convert.ToString(x + 1, 2).PadLeft(32, '0'));

x = ~x & (x + 1);

Console.WriteLine("Result is: " + Convert.ToString(x, 2).PadLeft(32, '0'));

Isolating The Rightmost 0-Bit

03:26

Changes the rightmost 0-bit into a 1 and leaves everything else the same

int x = 9;

x = x | (x + 1);

Console.WriteLine("result in binary is " + Convert.ToString(x,2));

Turning On The Rightmost 0-Bit

02:40

+
–

Conversion
2 Lectures
10:30

Two ways to convert a binary string to an integer

//1st way

int z = Convert.ToInt32("1000", 2);

Console.WriteLine(z);

//2nd way

string x = "1000";

int result = 0;

for (int i = 0; i < x.Length; i++)

{

if (x[i] == '1')

result += (int)Math.Pow(2, x.Length - i - 1);

}

Console.WriteLine(result);

Converting A Binary String To An Integer

05:00

Two ways to convert an integer to a binary string

//1st way

string result2 = Convert.ToString(10, 2); //Returns string “1000”

Console.WriteLine(result2);

//2nd way

int x = 10;

string result = "";

while (x > 0)

{

int remainder = x % 2;

x /= 2;

result = remainder.ToString() + result;

} //prepends, starts at far right bit and adds, so to get 4 in binary, it's 0, 00, 100

Console.WriteLine(result);

Converting An Integer To Binary

05:30

+
–

Cycling Techniques
2 Lectures
06:19

How to iterate through all bits in an integer

Combines checking if last bit is set technique with right-shift

//While loop continues while x is > 0, check if last bit is set and divide by 2 until x is 0.

int x = 8;

while (x > 0)

{

//Checking for set or unset bits

if ((x & 1) == 1)

{

//do something

}

x = x >> 1; //Divides x by 2

}

Cycling Through All The Bits

03:48

//Short way

~x

//Another short way

x = -x - 1

Toggling All The Bits

02:31

+
–

XOR ^ Techniques
3 Lectures
12:16

How to test if two integers are equal using XOR

//5 0101

//4 0100

int x = 5;

int y = 4;

if ((x ^ y) == 0)

Console.WriteLine("they're equal");

This technique can be used to determine the number of bits you would need to flip to convert one integer into another

int x = 15; //15 1111

int y = 4; //4 0100

int z = x ^ y;

Console.WriteLine("z in binary is" + Convert.ToString(z,2));

Testing Equality With XOR

04:57

How to swap variables without using a temp variable

int x = 5;

int y = 10;

x = x ^ y;

y = x ^ y;

x = x ^ y;

Console.WriteLine("x is now: " + x);

Console.WriteLine("y is now: " + y);

XOR Swap

03:53

How to solve the 'Use Bitwise Operators To Determine If An Integer Is Positive Or Negative' interview question.

Use Bitwise Operators To Determine If An Integer Is Positive Or Negative

03:26

+
–

Single Technique Interview Questions
5 Lectures
19:45

How to solve the 'How Do You Check The Equality of Two Integers Using Bitwise Operators?' interview question.

How Do You Check The Equality of Two Integers Using Bitwise Operators?

03:18

How to solve the 'Use BitWise Operators To Determine Whether An Integer Is Odd Or Even' interview question.

Use BitWise Operators To Determine Whether An Integer Is Odd Or Even

02:38

How to solve the 'Use Bitwise Operators To Determine Whether An Integer Is A Power Of 2' interview question.

Use Bitwise Operators To Determine Whether An Integer Is A Power Of 2

03:35

How to solve the 'Swap Two Integers With No Temporary Variable' interview question.

Swap Two Integers With No Temporary Variable

06:06

How to solve the 'Write A Function That Takes An Unsigned Integer And Returns The Number Of Set Bits It Has' interview question.

Write A Function That Takes An Unsigned Integer And Returns Number Of Set Bits

04:08

+
–

Multiple Technique Interview Questions
4 Lectures
18:11

How to solve:

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

Print smallest and largets numbers with same number of set bits as given int - 1

02:36

How to solve - continued

Given a positive integer, print the next smallest and the next

largest number that have the same number of 1 bits in their binary

representation.

Print smallest and largets numbers with same number of set bits as given int - 2

04:41

How to solve - continued

Given a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.

Print smallest and largets numbers with same number of set bits as given int - 3

02:36

How to solve:

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j)

Setting bits in a range amongst two 32-bit ints

08:18

About the Instructor

Software Tinkerers

We are dedicated to breaking down complicated subjects and explaining them so anybody can understand them.

We like to create software that is easy to use and easy to maintain. We work with a lot of Microsoft technologies particularly C#. We have written several applications in C# and like to work on open source projects.

- About Us
- Udemy for Business
- Become an Instructor
- Affiliate
- Blog
- Topics
- Mobile Apps
- Support
- Careers
- Resources

- Copyright © 2017 Udemy, Inc.
- Terms
- Privacy Policy and Cookie Policy
- Intellectual Property