Bit Manipulation Algorithms: DSA

Name: Bit Manipulation Algorithms: DSA
Rating: 4.4 (16 reviews)

Learn the working and the implementation of bit manipulation algorithms

Created bySujithkumar MA

Last updated 10/2024

English

English [Auto],

What you'll learn

Crack Problems on Bits and Bytes during coding interviews
Understand how to operate on bit level
Knowing all the tricks to solve complex problems using bitwise operators simply
Implement Bitwise Algorithms using Python 3

Coding Exercises

This course includes our updated coding exercises so you can practice your skills as you learn.

Course content

3 sections • 22 lectures • 2h 45m total length

Converting Decimal to Binary4:04
Explore bit manipulation by converting any decimal number to binary, using binary digits and weights like 8, 4, 2, 1, and understanding why radix is two.
Convering Binary to Decimal4:09
Explore how decimal numbers convert to binary by recognizing fixed weights for each place and summing powers of two, illustrated with decimal eleven, which equals binary 1011.
Representing negative numbers10:19
Learn to represent negative numbers using one’s complement, two’s complement, and sign magnitude; apply a right-to-left trick to compute two’s complement and read the sign bit (msb).
Bitwise Operators15:36
Master core bitwise operators—and, or, xor, not—through binary conversion and truth tables, with examples like five, six, ten, twelve and a primer on two's complement.
Results of Bitwise Operators7:41
Explore the bitwise and, or, and xor operators via their truth tables, highlighting how zero and one drive bit behavior and the key identities for clearing, setting, and complementing bits.
Bitwise shifting operators9:24
Learn bitwise shifting operators, including left and right shifts, how they move bits, and that left shifts multiply by 2^n while right shifts divide by 2^n.
Little Endian and Big Endian Architecture2:44
Explain how little endian and big endian architectures store values in registers and bytes in memory, using the 0x1234567 example to illustrate msb and lsb ordering.

Problem 1 - Checking whether the numbers are different7:43
Determine if two numbers have opposite signs using bitwise operators and xor logic, leveraging sign bits and two's complement to print same or different signs.
Problem 2 - Clear the LSB2:01
Learn to clear the least significant bit with a bitwise operator. See 7 become 6 and 9 become 8 in binary, showing the rightmost bit cleared while other bits stay.
Problem 2 (Continued)5:41
Apply the bitwise operation with the ones complement of one to clear the least significant bit, turning 15 into 14 and 11 into 10, illustrating bit-level end with one.
Problem 3 - Finding out the all alone element in an array9:22
Use bitwise xor to find the unique element by sequentially xoring elements from left to right, since pairs cancel out.
Problem 4 - Add +1 to a given number without using +14:05
Learn to add one to a number without using plus one by applying bitwise operators and the one complement trick, with examples like 5->6, 10->11, and 14->15.
Problem 5 - Multiplying by 2.5 without using multiplication operator4:51
Learn to multiply any number by 2.5 without using the multiplication operator by using bitwise left and right shifts and addition.
Problem 6 - Printing whether the number is a power of 2 or not13:41
Determine whether a given decimal is a power of two by counting ones in its binary representation with a bitwise approach, using end checks and right shifts.
Problem 7 - Finding out XOR of two numbers without using XOR operator4:25
learn to compute the xor of two numbers without the xor operator using (a & ~b) | (~a & b), illustrating exclusive or when a and b differ.
Problem 8 - Count the number of flippings that have to be done to convert A to B7:41
Compute the number of bit flips needed to convert one number to another by using xor to reveal differing bits and counting the ones, i.e., the hamming distance.
Problem 9 - Swap two nibbles in a byte7:04
This lecture explains swapping the two nibbles of an 8-bit byte using masks and shifts, demonstrates with examples such as 16 becoming 1, and outlines masking and shifting steps.
Problem 10 - Swapping two numbers using xor7:05
Demonstrate swapping two numbers with xor swap using bitwise operators, showing a = a xor b, b = a xor b, a = a xor b, with a Python example.
Problem 11 - Finding the absolute value of a number without using abs() function14:36
Compute the absolute value with bitwise operations only, with no branching or abs function, by creating a sign mask via right shift, adding it, then xor-ing with the mask.
Problem 12 - The Russian Peasant Algorithm to multiply two numbers9:50
Learn to multiply two numbers with the Russian peasant algorithm using bitwise shifting, doubling and halving, and adding when the second factor is odd, without using multiplication.
Problem 13 - Hamming Weight7:54
Learn to count ones in a number's binary representation using bitwise operators. Apply and with one and right shifts to compute the Hamming weight efficiently.
Problem 13.1 - Coding the Hamming Weight Problem5:33
Implement the hamming weight algorithm in python by counting ones in a non-negative integer's binary representation. Use a while loop, check the lsb, and right shift until zero.

Requirements

A basic programming knowledge is preferred, but not compulsory

Description

Crack the coding rounds and interviews whenever a question on bit manipulation is asked!

Welcome to the specific course on 'Bit Manipulation Algorithms'. This course will give you a deep understanding on how the numbers work as bits and bytes inside your computer and how to operate on bit level as a programmer?

The course will begin with the basics of converting decimals into bits, operating on those bits using operators such as Bitwise AND, OR, NOT and XOR and the most powerful operators like left and right shifts, the architectural features such as Little Endian and Big Endian.

Problems that are solved using Bitwise Algorithms:

1. Checking whether the two numbers have different signs

2. Clearing the Least Significant Bit

3. Finding out the all alone element in an array

4. Add 1 to the given number without using +1

5. Multiplying a number with 2.5 without using '*2.5'

6. Printing whether the given number is a power of 2

7. Finding out the XOR of two numbers without using XOR

8. Count the number of bits that have to be flipped to convert from A to B given two numbers A and B

9. Swap the two nibbles in a byte.

and so on.

The algorithms will be clearly explained and implementation will be done in anyone of your favorite programming languages. A basic knowledge in programming is preferred but not a strong requirement.

Who this course is for:

Beginner Software and Hardware Aspirants.

Bit Manipulation Algorithms: DSA

What you'll learn

Explore related topics

Coding Exercises

Course content

Fundamentals of Bit Level Operations!7 lectures • 54min

Algorithms and their Implementation15 lectures • 1hr 52min

Exercises0

Requirements

Description

Who this course is for: