The ultimate guide to bit manipulation for coding interviews. Developed by FAANG engineers, practice with real-world interview questions, and get interview-ready in just a few hours.

This course teaches bit manipulation, a powerful technique to enhance algorithmic and problem-solving skills. It is a critical topic for those preparing for coding interviews for top tech companies, startups and industry leaders. Competitive programmers can take full advantage of this course by running most of the bit-related problems in O(1) complexity.

The course will begin by educating you about the number system and its representation, decimal and binary, followed by the six bitwise operators: AND, OR, NOT, XOR, and bit-shifting (left, right).

You will receive ample practical experience working through practice problems to improve your comprehension.

Upon completing this course, you will be able to solve problems with greater efficiency and speed.

Grokking Bit Manipulation for Coding Interviews

# Introduction

In this lesson, we discuss the subsets of a given input. This is one of the most popular questions asked in coding interviews.

Companies that have asked this in their coding interview are Apple, Microsoft, Amazon, Facebook, and many more.

# Problem Statement

We need to write a program that finds all possible subsets ( the power set) of a given input. The solution set must not contain duplicate subsets.

```
Input: [1, 2, 3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

```
Input: [100]

Output: [[], [100]]

```

**Explanation:** The subsets of any given input are equal to its power set.

> if, input n = 3, then, powerset => $2^{n}$ = $2^{3}$  = 8.

Assume input has a length greater than or equals to 1.

**Hint:** Use left-shift operator to achieve this.

# Solution
In this program, we find the power set of a given input using bitwise operations.

In general, if we have `n` elements then the subsets are $2^{n}$ subsets.

So for every possible case of having at least two elements, we can see that an element is present and not present in the subsets.

Think of a solution that is iterative, uses bitwise operators, and generates the powerset.

Here is how we generate each subset using the outer-loop variable `counter`. Here is a table indicating how the value gets generated based on the counter input.




In this lesson, we find the power set of given input without duplicates.

Getting Started

Number Systems, Bitwise, and Binary

Bitwise AND

Bitwise OR

Bitwise NOT

Bitwise XOR

Bit Shifting - Left, Right

Bitwise LeftShift Problems

Bitwise RightShift Problems

Final Thoughts

Subsets / Powerset

Introduction

Problem Statement