# II. Implementation
Hiểu đơn giản là bắt tay vào code.
## II.1 - Bitmask
Là một kĩ thuật tận dụng những toán tử(hay là cái gì đấy) liên quan tới `bit` để giải quyết một cách hiệu quả những bài toán yêu cầu sử dụng `bit`
### II.1-a: IsZero(X)
Là 1 hàm kiểm tra xem số nguyên đó có bằng 0 không, nó trả về giá trị `bool`.
```cpp
bool IsZero(int x)
{
if(x==0){
return true;
}
return false;
}
int x = 0;
int y = 1;
bool IsZero(int x) return x == 0;
if(IsZero (x))
{
cout << "x là số 0"
}
cout << "\n";
if(!IsZero (y))
{
cout << "y không là số 0";
}
```
**Output**
```
x là số 0
y không là số 0
```
### II.1-b: IsOdd(X) IsEven(X)
Là 2 hàm kiểm tra số chẵn và lẻ, Odd là lẻ và even là chẵn và trả về giá trị bool.
```cpp
bool IsOdd(int x)
{
return (x & 1);
}
bool IsEven(int x)
{
return !(x & 1);
}
int x;
cin >> x;
if(IsOdd(x))
{
cout << "x là số lẻ";
}
cout << "\n";
if(IsEven(x))
{
cout << "x là số chẵn";
}
```
**Input**
```
1
```
**Output**
```
x là số lẻ
```
**Giải thích**
Để ý các số chẵn lẻ ta thấy:
|Số thập phân|Nhị phân|Bit cuối|Loại|
|------------|--------|--------|----|
|4 |100 |0 |chẵn|
|5 |101 |1 |lẻ |
|6 |110 |0 |chẵn|
|7 |111 |1 |lẻ |
Từ đó ta suy ra chỉ cẩn kiểm tra bit cuối ta có thể biết số đó là chẵn hay lẻ
### II.1-c: IsPowerOfTwo(X)
Là hàm kiểm tra 1 số có phải một số có thể viết dưới dạng 2^n^ không.
```cpp
bool IsPowerOfTwo(long long x)
{
return (x > 0 && (x & (x - 1)) == 0);
}
```
Để ý các số cần tìm ta thấy:
|Số thập phân|Nhị phân|
|------------|--------|
|4 |100 |
|4 - 1 = 3 |011 |
|8 |1000 |
|8 - 1 = 7 |0111 |
Để ý, ta thấy số ngay trước số có thể viết dưới dạng 2^n^ không có bit nào trùng, vì vậy chỉ cần kiểm tra xem số ngay trước nó có trùng bit nào hay không và đảm bảo rằng `x > 0`
### II.1-d: IsPowerOfFour(X) IsPowerOfPowerOfTwo(X, K)
Là hàm kiểm tra xem nó có phải lũy thữa của 4 hay không, không có sẵn trong c++.
```cpp
//đã include cmath
bool IsPowerOfTwo(long long x)
{
return (x > 0 && (x & (x - 1)) == 0);
}
bool IsPowerOfFour(long long x)
{
if (!IsPowerOfTwo(x)) return false;
long long r = sqrt(x);
return r * r == x && IsPowerOfTwo(r);
}
```
Để kiểm tra xem liệu một số có thể viết dưới dạng 4^n^ hay không.
```cpp
bool IsPowerOfTwo(long long x)
{
return (x > 0 && (x & (x - 1)) == 0);
}
bool IsPowerOfPowerofTwo(long long x, long long k)
{
if(x <= 0) return false;
if(!IsPowerOfTwo(x)) return false;
int p = 0;
while(x > 1)
{
x >>= 1;
p++;
}
return (p % k == 0);
}
```
Để kiểm tra xem liệu một số có thể viết dưới dạng 2^p×k^ hay không.
### II.1-e: CheckBit(X, B) SetBit(X, B) UnsetBit(X, B) ToggleBit(X, B)
`CheckBit(x,b)`: check biến thứ B xem nó có đang bật hay không, nghĩa là tại vị trí thứ b của x thì có phải số 1 không
```cpp
bool CheckBit(int x, int b)
{
if((x & (1 << b)) == 0)
{// & là kiểm tra xem 2 dãy bit đó có bit
//cùng bằng 1 thấp nhất, 1 << b là tạo 1 dãy bit toàn 0 chỉ có ở
//vị trí b là 1
return false;
}
return true;
}
```
`setbit(x,b)`: bật bit thứ b lên nếu nó = 0.
```cpp
int setbit(int x, int b)
{
return x | (1 << b);
// toán tử '|' hay còn gọi là toán tử OR
// nó giữ lại tất cả bit khác và chỉ bật bit thứ b lên.
// OR hoạt động theo kiểu nếu 1 trong 2 bằng 1 thì nó sẽ = 1.
}
```
`unsetbit(x,b)`: ngược lại với setbit, nó tắt thằng đang mở.
```cpp
int UnsetBit(int x, int b)
{
return x & ~(1 << b);
}
// code này hoạt động bằng cách cho 1 dãy bit và chỉ có ở vị
// trí b bằng 1, đảo lại hết tức là nêu tại b = 1 thì giờ b = 0
// tại b,nếu x = 1 hay 0 thì nó vẫn trả về 0
```
`togglebit(x,b)`: nghịch đảo bit tại vị trí b của x.
```cpp
int togglebit(int x,int b)
{
return x ^ (1 << b);
//code hoạt động như sau:
//tạo ra 1 dãy bit chỉ có b bật
//sử dụng toán tử XOR(^) để nếu b đang bật thì tắt và nếu b tắt thì không làm gì
//lí do hoạt động: nếu tại vị trí b, b = 1 thì toán tử sẽ biến nó thành ngược lại
}
```
**Giải thích toán tử `XOR`**
Ta có `x = 1010`, `b = 2`
- Đầu tiên, ta có `1 << b` tạo thành một chuỗi bit `0100`
- Tiếp theo, toán tử `XOR` chỉ đảo bit khi nó được kêu phải làm, và chuỗi bit `0100` chính là câu lệnh
- Tại vị trí số 3, tức là `1` trong chuỗi `0100`, toán tử XOR sẽ đảo bit tại đúng vị trí đó trong x.
- Kết quả: `x = 1010` → `x = 1110`
### II.1-f: AssignBit(X, B, V)
Là bật hoặc tắt bit tại vị trí b của x theo v.
```cpp
int AssignBit(int X, int B, int V)
{
if (V == 0)
return X & ~(1 << B); //tắt bit, có giải thích ở unsetbit
else
return X | (1 << B); //bật bit,giải thích ở setbit
}
```
### II.1-g: ToBinary(X)
Là chuyển đổi từ hệ thập phân sang nhị phân.
```cpp
string ToBinary(int n)
{
string bin = "";
while(n > 0)
{
bin = char('0' + (n % 2)) + bin;
n /= 2;
}
if(bin == "") bin = "0";
return bin;
}
```
Dùng quy tắc chia dư cho hai.
### II.1-h: ToOctet(X) ToHex(X)
ToOctet(X):Là chuyển đổi từ hệ thập phân sang bát phân.
```cpp
string ToOctet(int n)
{
string oct = "";
while(n > 0)
{
oct = char('0' + (n % 8)) + oct;
n /= 8;
}
if(oct == "") oct = "0";
return oct;
}
```
Áp dụng tương tự như `ToBinary`
Là chuyển đổi từ hệ thập phân sang thập lục phân(16).
```cpp
string ToHex(int n)
{
if(n == 0) return "0";
string hex = "";
char hdigits[] = "0123456789ABCDEF";
while(n > 0)
{
hex = hdigits[n % 16] + hex;
n /= 16;
}
return hex;
}
```
Áp dụng tương tự như `ToBinary`, nhưng xử lí phần dư từ 10 → 15 bằng chữ cái A → F.
### II.1-i: XorSwap(X, Y)
Hoán đổi 2 biến mà không cần biến thứ 3, nhưng chậm hơn swap bình thường, áp dụng bit.
```cpp
int x = 3,y = 5;//đổi ra bit thì 3-->0011,5-->0101
x = x ^ y;
//toán tử xor nếu 2 bit bằng nhau thì nó tắt và ngược lại.
//code trên sử dụng toán tử xor cho 3 và 5 hay 0011 với 0101
//suy ra x bây giờ bằng 0110 và y vẫn bằng 0011.
y = x ^ y;
//lúc này đổi 0110 với 0011 suy ra y=0101=5.
x = x ^ y;
//đổi 0110 với 0101 suy ra x=0011=3.
//vậy là đã đổi giá trị của x và y.
```
### II.1-j: BitLength(X) Log2(X)
Tính số bit cần dùng để biểu diễn X mà không có số 0 ở đầu
```cpp
int bitLength(int X)
{
if (X == 0) return 1;
int len = 0;
while (X > 0)
{
len++;
X >>= 1; //dịch sang phải 1 bit, đồng thời bỏ luôn bit cuối
}
return len;
}
```
Tìm `n` sao cho 2^n^ = x.
```cpp
//Đã include cmath
cout << log2(x);
```
### II.1-k: CountSetBit(X),CountUnsetBit(X)
CountSetBit(X): đếm số bit bật - đếm số lượng số bật có trong dãy bit của 1 số.
```cpp
int CountSetBit(int x)
{
int count = 0;
while (x != 0)
{
if (x & 1) count++;
x >>= 1;
}
return count;
}
```
CountUnsetBit(X): đếm số bit tắt.
```cpp
int CountUnsetBit(int x)
{
int count = 0;
while (x != 0)
{
if (!(x & 1)) count++;
x >>= 1;
}
return count;
}
```
### II.1-l: CountTrailingZero(X) CountTrailingOne(X)
Là 2 thuật toán kiểm tra xem có bao nhiêu số 0 hoặc 1 liên tiếp trong dãy bit của số x tính từ phải sang trái, CountTrailingZero(X) là kiểm tra số 0, CountTrailingOne(X) là kiểm tra số 1. Nói cách khác là kiểm tra chia cho 2 hết hay dư tối đa bao nhiêu lần.
```cpp
int CountTrailingZero(x)
{
int d = 0;
while(x & 0 and x > 0)
{//nếu bit cuối của x bằng 0 và x>0 sẽ lặp.
d++;//biến đếm cộng lên.
x = x >> 1;//cho x dịch trái 1 lần rồi gán lại vào x.
}
if(x == 0)
{
return "vô hạn"
}// nếu x=0 thì bit cuối sẽ luôn là 0 dù có dịch trái
return d;
}
int CountTrailingZero(x)
{//tượng tự như trên chỉ khác đk while.
int d = 0;
while(x & 1)
{
d++;
x = x >> 1;
}
return d;
}
```
### II.1-m: CountLeadingZero(X) CountLeadingOne(X)
Giống CountTrailingZero(X) CountTrailingOne(X) nhưng đếm từ trái sang.
### II.1-n: LeastSignificantBit(X) MostSignificantBit(X)
Tìm vị trí bit được bật ở ngoài cùng.
```cpp
int LeastSignificantBit(int x)
{
int index = 0;
while (x % 2 == 0)
{
x >>= 1;
index++;
}
return index;
}
```
Tìm vị trí bit được bật ở trong cùng.
```cpp
int MostSignificantBit(int x)
{
int index = 0;
while (x > 1)
{
x >>= 1;
index++;
}
return index;
}
```
### II.1-o: BitLeftRotation(X, N) BitRightRotation(X, N)
Là đẩy các số 1 của dãy bit qua hoặc qua phải n lần. (Chỉ dùng cho 32 bit được thôi với code này)
```cpp
unsigned int BitLeftRotation(unsigned int X, int N)
{
return (X << N) | (X >> (32 - N));
}
unsigned int BitRightRotation(unsigned int X, int N)
{
return (X >> N) | (X << (32 - N));
}
```
### II.1-p: SubmaskEnumeration(X)
### II.1-q: SignOf(X) IsPositive(X) IsNegative(X)
Cả 3 hàm trên đều để kiểm tra xem có phải là số âm, dương không, signof(x) trả về int 1, 0, -1 để biểu thị còn 2 cái con lại trả về bool.
```cpp=
int SignOf(X)
{
if(x > 0) return 1;
if(x < 0) return -1;
return 0;
}
bool IsPositive(X)
{
if(X>0) return true;
return false;
}
bool IsNegative(X)
{
if(x<0) return true;
return false;
}
```
### II.1-r: HasOppositeSign(X, Y)
```cpp
bool HasOppositeSign(X, Y)
{
if ((X < 0 && Y > 0) || (X > 0 && Y < 0)) return true;
return false;
}
```
### II.1-t: BitAbs(X)
Giá trị tuyệt đối
```cpp
int bitabs(int x)
{
int y = x >> 31;
(x + y) ^ y;
}
```
### II.1-u: BitMin(X, Y) BitMax(X, Y)
```cpp
int BitMin(X, Y)
{
return x < y ? x : y;
}
int BitMax(X, Y)
{
return x < y ? y : x;
}
```
### II.1-v: LexicoNextBitPermutation(X) LexicoPrevBitPermutation(X)
### II.1-w: NextPowerOfTwo(X) PrevPowerOfTwo(X)
### II.1-x: GrayCode(X) InverseGrayCode(X)
### II.1-x: ReverseBit(X)
```cpp
int ReverseBits(int n)
{
int ans = 0;
while (n > 0)
{
ans <<= 1;
if (n & 1 == 1) ans |= 1;
n >>= 1;
}
return ans;
}
```
### II.1-z: GenAllBinary(N) GenAllTernary(N) GenAllQuaternary(N) GenAllGrayCode(N)
## II.2 - Bitmask Bultin
### II.2-a: Count Set Bit __builtin_popcount**(X) (**=NULL,L,LL)
### II.2-b: Count Trailing Zeros __builtin_ctz**(X) (**=NULL,L,LL)
### II.2-c: Count Leading Zeros __builtin_clz**(X) (**=NULL,L,LL)
### II.2-d: Parity Check __builtin_parity**(X) (**=NULL,L,LL)
### II.2-e: Least Significant Setbit __builtin_ffs**(X) (**=NULL,L,LL)
### II.2-f: Bit Left Rotation __builtin_rotateleft**(X, N) (**=8,16,32,64)
### II.2-g: Bit Right Rotation __builtin_rotateright**(X, N) (**=8,16,32,64)
### II.2-h: Bit Swap Endians __builtin_bswap**(X) (**=8,16,32,64)
Sign in with Wallet
Connect another wallet