Set Operation using Bit in C++

Home / Set Operation using Bit in C++

Set Operation using Bit in C++

November 24, 2015 | Article | No Comments

Set operations are operations over a set. In this article we will discuss about how to perform some set operation with integer and bit operation. With this we can do at most 32 member on a single set (32 is the total number of bit on 32-bit machine). But before that, let’s check the basic concept first.

The Basics

The core of our operation is bit manipulation, the bit-wise operations. What are bit-operation we have? There are & (and), | (or), ~ (not), and ^ (xor) respectively. You must be familiar with the first three as they are the close relative of their boolean forms (&&, ||, and !). Just a remainder, let’s check the truth tables for each of statements:

A B !A A && B A || B A ^ B
0 0 1 0 0 0
0 1 1 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0

Where 0 denotes false and 1 denotes true.

The bit-wise version are not different, except interpreting the argument as true or false, they operate on each bit of arguments. Thus, if A is 1011 and B is 1100 then:

  • A & B = 1000
  • A | B = 1111
  • A ^ B = 0111
  • ~A = 0100 (actually the number is depend on the type A, here we have A is 4-bit integer so the inverse is quite straightforward).

Another two operator that must not be forgotten are shift left << and shift right >>. The shift like its name shift each position of bits to direction (left is left and right is right). The former, a << b, shifts a to the left by b positions; the latter, a >> b, does the same but shifts right. For non negative values (and we only interested on them), the newly exposed bits are fill with zero. We can simply say that the left shifting by b as multiplication by 2 power b while right shifting means divide it by 2 power b.

Our most common use of shifting is to access a particular bit, for example: 1 << x is a binary number with bit x set and the others clear.

The Set Operation

The set operations are operation with the operator is applied over a set. In this concept of bit-wise, we represent a set on a domain of up to 32 values (if we are using 64-bit integer, it would be 64), with every single bit representing a member which can be present (denoted by 1) or absent (denoted by 0). ALL_BITS denote a number with all 1 bits set to 1 (the universe set). The operations are quite straightforward. Here is the list of bit operation we have:

  1. Set union A | B
  2. Set intersection A & B
  3. Set substraction A & ~B
  4. Set complement ALL_BITS ^ A
  5. Setting a bit A |= 1 << bit
  6. Clear a bit A &= !(1 lt;< bit)
  7. Test a bit (A & 1 << bit) != 0

Do we have more? šŸ˜€

,

About Author

about author

xathrya

A man who is obsessed to low level technology.

Leave a Reply

Your email address will not be published. Required fields are marked *

Social media & sharing icons powered by UltimatelySocial