Fun with bits - topcoder article study

May 11, 2017

Introduction

It is so interesting experience to play rookie 3 contest. Julia spent a lot of days after the contest to play with one algorithm called Maximum score. She wrote a blog documented her experience, and then she likes to study a topic - use bits of an integer to represent a set. The topic is about a set, and also using bit manipulation.

Fun with bits

Top coder - fun with bits, the article link is here.

Take some notes:
Use bits of an integer to represent a set. Not only does it produce an order-of-magnitude improvement in both speed and size, it can often simplify code at the same time.

Go over the most popular set manipulations in the following:

Set union         
A | B

Set intersection
A & B

Set subtraction
A & ~B

Set negation
ALL_BITS ^ A

Set bit
A |= 1 << bit

Clear bit
A &= ~(1 << bit)

Test bit
(A & 1 << bit) != 0

Extracting every last bit

Counting out the bits