Bitwise Operators (and BSets)

Question 1

How to add to a bitset

Answer 1

1. Create a binary value with the specific position set as 1
   In python: 1 &laquo_space;(item - 1) - meaning, take 1 bit, and move it left (item-1) positions
2. Then use the OR operator |= against the bitset, to actually update the value

Question 2

How to remove an element from a bitset

Answer 2

1. Create a binary value with the specific position set as 1
   In python: 1 &laquo_space;(item - 1)
2. Then use the XOR operator ^= against the bitset

XOR, exclusive OR, an output bit is 1 when the elements are different, and 0 when the elements are the same

Question 3

How to check if an element is in a bitset

Answer 3

Take the elements, shift it right to the element u wish to check, so elems&raquo_space; (item - 1)

And then AND it against 0001, which will check if the right most bit is 1, and if it is, then the element is in the bitset

Question 4

How to calculate the length of a bitset

Answer 4

You need to get the bitlength, and then loop through and check if the element is in the bitset

so O(|elements|) or O(num of elems)