Bits

Matthew Xia, Brian Law

Announcements

Member Presentations open

tinyurl.com/CSPresentation25 (Raw Link)

Hope you all did well on the December USACO contest!!

​

​

Advanced Problem Set

• https://qoj.ac/problem/5523
• https://codeforces.com/problemset/problem/1804/E
• https://usaco.org/index.php?page=viewproblem2&cpid=1327
• https://usaco.org/index.php?page=viewproblem2&cpid=1452

​

Binary Representation of numbers

• A number in binary (base 2) is made up of only 1s and 0s.
• Each digit represents a power of 2

​

​

2 → 10

3 → 11

5 → 101

11 → 1011

100 → 1100100

​

Bit Operations

AND

00101 & 10111 = 00101

OR

00101 | 10111 = 10111

NOT

~00101 = 11010

XOR

00101 ^ 10111 = 10010

Properties of Bit Operations

• XOR and NOT are their own inverse operation
• x ^ x = 0
• ~~x = x
• Useful for xor hashing
• Prefix sums?
• AND and OR are idempotent
• You can apply them multiple times without changing the result
• a & b & b & b & a = a & b
• a | b | b | a | b | b = a | b

Bit Operations - Example

https://codeforces.com/contest/579/problem/A

You are working in a laboratory and are raising bacteria in a box. Each morning, you can place any number of bacteria in the box. Each night, the number of bacteria in the box doubles. You need to make an observation when there is exactly K bacteria. What is the minimum number of bacteria you need to add to the box?

​

Solution

Let’s look at K as a binary number. Let n be the number of set bits in K. We claim that the answer is n.

First let’s show that we can not do better than n. Each time we double the number of bacteria, the number of set bits does not change. Everytime we add g bacteria into the box, we can increase the number of set bits by at most g. Therefore a lower bound on the number of bacteria added is n.

​

Solution (continued)

We will provide a construction adding n bacteria. Let the index of the largest bit in K be d. If bit a is on in K, we will add 1 bacteria on day d - a, which will result in the ath bit being set on the dth day.

In other words, we are counting the number of “1” bits in K, which can be implemented using __builtin_popcount(x) in C++ or x.bit_count() in Python.

Representing subsets as integers

Each subset of a set can be represented as a string of bits

• Each bit corresponds to a value in the set
• A 1 means that element is included in the subset
• A 0 means it is not included

For the set {1, 2, 3, 4, 5, 6}

the subset {2, 3, 5} would correspond to the bits 011010

011010 in binary converted to decimal is 26

This is the bitmask of the subset

Bitmask DP

• Dynamic programming where each state is a subset
• Subsets can be represented as integers
• Works if size of the original set is small, as there are a total of 2^N subsets
• For competitive programming purposes, this will generally not exceed time limits if N ≤ 20

​

• Storing subsets as integers is memory efficient
• Transitions can be done quickly using bit operations

Bitmask DP - example

https://atcoder.jp/contests/dp/tasks/dp_o (Also known as 01-Matrix Permanent)

​

​

Sample

Solution

Let dp[i][j] is the number of pairings of the first i men and the subset of women represented by the bitmask j.

​

​

​

What this essentially means is that for the first i men, you want to find the number of pairings for each possible set of women selected j. For each set, you iterate over the potential pairings k for the ith man, then you add the number of pairings for the first i-1 men and the set j excluding k.

This runs in O(N*2^N)

Further Reading

• Iterating over submasks
• Enumerate all subsets of a set (the set is given as a bitmask)
• Bitset
• Use bit operations to speed up certain operations on a massive scale
• XOR Hashing
• Use the unique self-inverting property of XOR to hash sets
• XOR Basis
• Introduction to linear algebra! Varied uses.

Meeting Attendance

784074