Bit Operation and Bitmap

Learn something about bit

Owing to the binary system inside the computers, bit becomes important when programing.

Bit Operator

operator	function
&	and
^	xor
|	or
~	not
<<	shift left
>>	shift right

These are the basic operators of bit. The meanings are the same as in logic.

Common Use

&

& is often used to do the binary fetch operation(二进制取位操作).
e.g. num&1 → get the last bit of num → judge num’s parity.

|

| is often used to do the unconditional assignment(无条件赋值).
e.g. num|1 → change the last bit of num into 1forcibly → let num minus 1 and get the closest even number.

^

1. The inverse operation of ^ is itself; it can be used to inverse one bit of number.
   e.g. num^1 → inverse the last bit.
2. ^ can also be used to do simple encryption.
3. Swap two numbers. formula → x^=y^=x^=y

~

~ inverse all the bits in the number, thus we must pay attention to the sign.CAUTION

<<

a<<b moves a to the left by step of b, i.e. multiples a by 2^b .

>>

a>>bmoves a to the right by step of a, i.e. divide a by 2^b(integer).
p.s. The Greatest Common Divisor

1. The Euclid Algorithm gcd(a,b)=gcd(b,a%b)
2. The Binary Algorithm It’s based on Euclid algorithm.
   a. a,b both even → gcd(a,b)=2*gcd(a/2,b/2)
   b. a odd, b even(or another possiblity) → gcd(a,b)=gcd(a,b/2)
   c. a,b both odd → gcd(a,b)=gcd(b,a-b)

Then use recursion to realize it.

Bitset And Bitmap In C++

After learning bit, there are something further.

Bitset

bitset is a encapsulated class in C++. It provides operations on bits.
The way to access each bit is similar to the array.a[3]
The way to output it is cout.
Following are the ways to initial a bitset.

#include <bitset>
#include <iostream>
using namespace std;
bitset<16> a(string"110101001");//match from right on.
      //match from left on only when the bitset is too short.
bitset<4> b(16);//transform int.
bitset<23> c(string("1111110000"),5,3);// get the string from pos 5 by 3 steps.
int main()
{
    cout<<a<<endl<<b<<endl<<c<<endl;
    return 0;
}

operation	function
a.any()	if there are some bit as 1
a.none()	if all 0
a.count()	count 1
a.size()	how many bits
a.test(pos)	if a[pos]==1
a.set() (reset(),the opposite)	set all bits in a as 1
a.set(pos) (reset(),the opposite)	set a[pos] as 1
a.flip()	inverse all bits
a.flip(pos)	inverse a[pos]
a.to_ulong()	transform a into unsigned long

Bitmap

Bitmap is a good way to store unique numbers.(similar to bool, but more space-saving)
Usually, one int(integer) in the computer occupies 4byte i.e. 32 digit, but sometimes we use int to do countings. In specific occassion we only use it to judge true or fasle, thus it’s better to use bool. However, one bool occupies 1 byte, i.e. 8 digit, which is unreasonable. Hence, we want to use only one bit to do the work.
e.g. There are nonrepetitive ints between [1,max], and max is alarge integer.

#include<iostream>
using namespace std;
int a[1000];
void insert(int x)
{
    int i=x>>5, j=x%32;
    a[i]|=(1<<j);
}
int main()
{
    insert(15);
    cout<<a[0];
    return 0;
}

And since we know how to use Bitset, we can change the array into a bitset and the operations will be largely simplified.