# Kiểm tra bài vở
[TOC]
## I. Implementation Fundamentals
### I.1 – Statements (Câu lệnh)

### I.1-a: Single Statement
Một câu lệnh kết thúc bằng ;
vd:
`int x;`
`cin >> x;`
`cout << x;`
### I.1-b: Compound Statement {...}
Nhiều câu lệnh gói trong {} (block).

if (x > 0) {
    cout << "True";
    x--;
}

### I.1-c: if else – Rẽ nhánh.

if (a > b) cout << "a";
else cout << "b";

### I.1-d: switch case – So sánh nhiều giá trị của 1 biến.

switch (n) {
    case 1: cout << "One"; 
	break;
    case 2: cout << "Two"; 
	break;
    default: cout << "Other";
}

### I.1-e: ternary operator – Toán tử 3 ngôi, viết gọn if else.
`int val = (a < b ? a : b);`

### I.1-f: while – Vòng lặp khi điều kiện còn đúng.

while (n > 0) {
cout << n; 
n--; }

### I.1-g: do while – Luôn chạy ít nhất 1 lần.

do { cout << n; n--; } 
while (n > 0);

### I.1-h: for – Lặp với bộ đếm.

for (int i = 0; i < 5; i++) cout << i;

### I.1-i: range-for – Lặp qua container.

vector<int> v = {1,2,3};
for (int x : v) cout << x;

### I.1-j: continue
Bỏ qua phần còn lại của vòng lặp, chuyển sang lần lặp tiếp.

### I.1-k: break
Thoát khỏi vòng lặp.

### I.1-l: goto
Nhảy tới nhãn(ít dùng)

### I.2 - Int Types(kiểu số nguyên)
Kiểu số nguyên cơ bản.
Theo chuẩn C++: kích thước ít nhất 16 bit (≥2 byte), nhưng trong hầu hết các hệ thống hiện đại nó là 32 bit (4 byte).
### I.2-a: int (>=2 byte)
-2,147,483,648 -> 2,147,483,647 (nếu 32-bit)
### I.2-b: unsigned int
Giống int nhưng không có số âm.
Khoảng giá trị:
0 -> 4,294,967,295 (nếu 32-bit)
Dùng khi chắc chắn giá trị luôn ≥ 0 (ví dụ: số lượng phần tử).
### I.2-c: long long
Được đảm bảo ít nhất 64 bit.
Rất phổ biến trong contest, vì int dễ bị tràn số khi xử lý giá trị lớn hơn 2e9.
Khoảng giá trị:
-9,223,372,036,854,775,808 → 9,223,372,036,854,775,807

### I.2-d: unsigned long long
Giống long long nhưng không âm
Khoảng giá trị:
0 → 18,446,744,073,709,551,615
### I.2-e: short
Ít nhất 16 bit (thường là 2 byte)
Khoảng giá trị (16-bit):
-32,768 → 32,767

### I.2-f: unsigned short
Giống short nhưng không âm
Khoảng giá trị:
0 → 65,535
### I.2-g: int8_t
đúng 8 bit (–128 → 127)
### I.2-h: int16_t
đúng 16 bit (–32,768 → 32,767)
### I.2-i: int32_t
đúng 32 bit.
### I.2-j: int64_t
đúng 64 bit.
### I.2-k: uint8_t
unsigned 8 bit (0 → 255)
### I.2-l: uint16_t
unsigned 16 bit
### I.2-m: uint32_t
unsigned 32 bit
### I.2-n: uint64_t
unsigned 64 bit
### I.2-o: size_t
Kiểu unsigned integer đặc biệt, được dùng cho kích thước hoặc chỉ số mảng/vector
Được định nghĩa trong <cstddef>
Kích thước phụ thuộc vào hệ điều hành:
32-bit OS: size_t là 32 bit
64-bit OS: size_t là 64 bit
### I.2-p: ssize_t (C++20)
Giống size_t nhưng có dấu (signed)
Dùng khi ta cần biểu diễn cả số âm trong phép tính với kích thước hoặc chỉ số

### I.3 - Float Types(kiểu số thực)
### I.3-a: float
4 byte(32 bit, có thể làm tròn đến 6-7 số thập phân)
### I.3-b: double
8 byte(64 bit, có thể làm tròn 12-13 số thập phân)
### I.3-c: long double
Kích thước ≥ 10 byte (80, 96 hoặc 128 bit tùy máy)
Độ chính xác cao hơn double.
### I.4 - Char & String Types(Ký tự và chuỗi)
### I.4-a: char
Kiểu cơ bản, 1 byte (8 bit).
Thường lưu 1 ký tự ASCII (‘a’, ‘A’, ‘1’, ‘*’...)
### I.4-b: signed char
signed char: giá trị từ –128 → 127
### I.4-c: unsigned char
unsigned char: 0 → 255.
### I.4-d: string
Kiểu chuỗi động của STL
có nhiều hàm: a.size(), a.substr(), a.find()
### I.4-e: string_view
Cho phép “nhìn” vào chuỗi mà không copy dữ liệu
### I.4-f: fstream
Đọc file
### I.4-g: ifstream
Ghi file
### I.4-h: ofstream
Đọc và ghi
### I.4-i: stringstream
Cho phép gán giá trị chuỗi như stream
### I.4-j: istringstream
Cho phép xử lý chuỗi như stream (dùng >>)
### I.4-k: ostringstream
Cho phép xử lý chuỗi như stream (dùng <<)
### I.4-l: char8_t (C++20)
Dùng để lưu ký tự trong Unicode.
char8_t: UTF-8 (1 byte/ký tự).
### I.4-m: char16_t
char16_t: UTF-16 (2 byte).
### I.4-n: char32_t
char32_t: UTF-32 (4 byte).
### I.4-o: istream
Nhập chuẩn
### I.4-p: ostream
Xuất chuẩn
### I.4-q: cin
Nhập từ bàn phím
### I.4-r: cout
in ra màn hình
### I.4-s: cerr
In lỗi
### I.4-t: clog
In log
### I.4-u: Escape Character ('\n', '\\', '\'', '\"', ...)
Escape character: ký tự đặc biệt bắt đầu bằng \
'\n' : xuống dòng.
'\t' : tab.
'\\': in dấu \.
'\"': in dấu ".
### I.4-v: Escape Sequence ('\nnn', '\o{nnn}', '\xnnn', '\x{nnn}', ...)
Escape sequence: dạng số/mã:
'\x41' = 'A' (theo hệ 16).
'\101' = 'A' (theo hệ 8).
### I.6 - Literals (Hằng số trong code)
### Kiểu số nguyên:
### I.6-a: Long Literal (1L)
1L = long
### I.6-b: Unsigned Long Literal (1U)
1U = unsigned
### I.6-c: Long Long Literal (1LL)
1LL = long long
### I.6-d: Unsigned Long Long Literal (1ULL)
1ULL = unsigned long long
### Hệ cơ số:
### I.6-f: Signed Size Literal (1Z) (C++23)
1Z = size_t
### I.6-g: Octal Literal (0123)
0123 = octal(hệ 8)
### I.6-h: Hex Literal (0x123)
0x123 = hex(hệ 16)
### I.6-i: Binary Literal (0b123)
0a1010 = binary(hệ nhị phân)
### Hệ số thực:
### I.6-j: Float Literal (.1f)
.1f = float
### I.6-k: Double Literal (.1)
.1 = double
### I.6-l: Long Double Literal (.1L)
.1L = long double
### Ký tự/Chuỗi:
### I.6-m: Char Literal ('\n')
'a' = ký tự
### I.6-m: String Literal ("abc")
"abc" = chuỗi
### I.6-m: Raw String Literal (R"(raw\nstring)")
R"(raw\nstring)" = raw string (không xử lý \n)
### I.6-z: Digit Separator (123'456'789)
int x = 123'456'789; = 123456789
### I.7 - Cast(ép dữ liệu)
### I.7-a: C Cast (Type)(Data)
double x = 3.14;
int y = (int)x;
cout << y;
y = 3
### con trỏ:
void* p = &x;
double* dp = (double*)p;
### I.7-b: Static Cast static_cast<Type>(Data)

double x = 5.8;
int y = static_cast<int>(x);
y = 5

### con trỏ:

void* p = &x;
double* dp = static_cast<double*>(p);

### I.8 - Scoping
### I.9-
### I.10 – Unary Operators (Toán tử đơn ngôi)
### I.10-a: +x (Unary Plus)
Giữ nguyên giá trị của x, chỉ thể hiện rõ ràng là số dương
### I.10-b: -X Unary Minus
Đổi dấu giá trị của x
### I.10-c: !X Negation
Phủ định logic(not)
### I.10-d: ~X Bitwise NOT(Đảo bit)
Đảo tất cả các bit của số nguyên x
Vd:

int x = 5;   // 5 = 00000101 (8-bit)
int y = ~x;  // đảo hết → 11111010
cout << y;            // in ra 250 (nếu 8-bit)

### I.10-e: ++X Pre Increment
Tăng x lên 1 rồi trả về giá trị mới vừa +
### I.10-f: --X Pre Decrement
Giảm x xuống 1 rồi trả về giá trị mới -
### I.10-g: X++ Post Increment
Trả về giá trị cũ rồi mới tăng x
### I.10-h: X-- Post Decrement
Trả về giá trị cũ rồi mới giảm x
### I.11 - Arithmetic Operators(Toán tử số học)
### I.11-a: A+B Addition Plus
Cộng
### I.11-b: A-B Subtraction Minus
Trừ
### I.11-c: A*B Multiplication Multiply
Nhân
### I.11-d: A/B Division Div
Chia
### I.11-e: A%B Remainder Mod
Chia lấy dư(Modulo)
### I.12 - Comparison Operators(Toán tử so sánh)
### I.12-a: A<B Less LE
Nhỏ hơn
### I.12-b: A<=B Less Or Equal LEQ
Nhỏ hơn hoặc bằng
### I.12-c: A>B Greater GE
Lớn hơn
### I.12-d: A>=B Greater Or Equal GEQ
Lớn hơn hoặc bằng
### I.12-e: A==B Equal EQ
Bằng
### I.12-f: A!=B Not Equal NEQ
Không Bằng
### I.12-g: A<=>B Three-way Spaceship Operator
Dùng để so sánh 3 chiều: nhỏ hơn, bằng, lớn hơn trong 1 phép
### I.13 - Logic Operators(Toán tử logic)
### I.13-a: A&&B Logic And
Trả true nếu cả 2 điều kiện đều đúng
### I.13-b: A||B Logic Or
Trả true nếu ít nhất 1 điều kiện đúng
### I.13-c: There is no Logic Xor Operator
bool x = (A != B);
### I.13-d: Short Circuit
Trình biên dịch ngừng kiểm tra sớm nếu đã biết kết quả
### I.14 - Bitwise Operators(Toán tử Bit)
### I.14-a: A<<B Shift Left
Dịch tất cả các bit của A sang trái B lần
Mỗi lần dịch trái tương đương nhân với 2^B
Vd:

int x = 3;         // 00000011
int y = x << 2;    // 00001100 = 12

## BONUS:P
### I.14-b: A >> B – Shift Right (Dịch phải)
Dịch toàn bộ bit của A sang trái B lần
Các bit mới bên phải được điền bằng 0
### I.14-c: A & B – Bitwise AND
Chỉ trả về 1 khi cả hai bit đều 1, ngược lại là 0
Ví dụ:
A = `00001101` (13)
B = `00001010` (10)
A & B = `00001000` (8)
### I.14-d: A | B – Bitwise OR
Trả về 1 nếu ít nhất một bit bằng 1
Ví dụ:
A = `00001101` (13)
B = `00001010` (10)
A | B = `00001111` (15)
### I.14-e: A ^ B – Bitwise XOR (Exclusive OR)
Trả về 1 nếu 2 bit khác nhau, ngược lại 0
Ví dụ:
A = `00001101` (13)
B = `00001010` (10)
A ^ B = `00000111` (7)
### I.14-f: ~A – Bitwise NOT (Đảo bit)
Đảo tất cả các bit: 1 -> 0, 0 -> 1
Vd:
A = `00001101` (13)
~A = `11110010` (tùy số bit, ví dụ 8-bit -> 242)

**II. Implementation**
-
**II.1-a:** **`IsZero(X)`**

Chuyển số x sang chuỗi nhị phân. Dùng phép `&` với x và một chuỗi toàn số 0. Nếu `x != 0` thì phép `&` sẽ trả về một chuỗi có bit khác 0.

int isZero (int x) {
    if (x == 0) {
        return true;
    }    
    else {
        return false;
    }
}

**II.1-b:** `IsOdd(X)` `IsEven(X)`

bool isOdd(int n) {
    return n & 1;
}

bool isEven(int n) {
    return !(n & 1);
}

**II.1-c:** `IsPowerOfTwo(X)`

Một số $n$ có giá trị bằng $2^k$ thì khi biểu diễn dưới dạng nhị phân chỉ có đúng 1 bit bật và còn lại là bit tắt.
Suy ra $n-1 = 2 ^ {k-1}$. Số $2 ^ {k-1}$ sẽ có $k-1$ bit bật, vì vậy dùng phép toán `&` với số này, nếu $n$ có đúng 1 bit bật thì trả về kết quả sẽ là 0 (False), còn nếu ngược lại thì kết quả trả về sẽ là 1 (True).

#include <iostream>

using namespace std;
	
bool IsPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}
	
int main() {
    int n; cin >> n;
   
    if(Ispoweroftwo(n)) cout << "YES";
    else cout << "NO";
    
	return 0;
}

**II.1-d:** `IsPowerOfFour(X)`
Số là lũy thừa của 4 nếu:
Nó là lũy thừa của 2 (IsPowerOfTwo(x))
Bit 1 duy nhất nằm ở vị trí chẵn
-> 0x55555555 (binary 0101...) chỉ có bit ở vị trí chẵn = 1
=> (x & 0x55555555) kiểm tra xem bit 1 của x nằm ở chỗ chẵn

#include <iostream>

using namespace std;
	
bool IsPowerOfFour(int x){
	return x > 0;
	&& (x & (x - 1)) == 0
    && (x & 0x55555555);
	}
	
    int main(){
	int n; cin >> n;
	
	if(IsPowerOfFour(n)) cout << "YES";
	else cout << "NO";
	}

### **II.1-e:** `CheckBit(X, B)` `SetBit(X, B)` `UnsetBit(X, B)` `ToggleBit(X, B)`

bool checkbit(int x, int b) {
	return (n & (1 << k));
}

int togglebit (int x, int b) {
	return n ^= (1 << k);
}

int unsetbit (int x, int b) {
	return n &= ~(1 << k);
}

int setbit (int n, int k) {
	return n |= (1 << k).
}

### **II.1-f** `AssignBit(X, B, V)`
Gán bit thứ B của X = giá trị V(0 hoặc 1)

int assignbit(int x,int b,int v) {
    if(v != 0 && v != 1){ 
	return x;
	}
	return (x & (~1 << B)) | (V << B)
	}
	
	int main(){
	int B, V, X; cin >> X >> B >> V
	
	x = assignbit(X, B, V);
	
	cout << bitset<8>(x);
	}

    
    

### **II.1-g:** `ToBinary(X)` `ToOctet(X)` `ToHex(X)`

string tobinary(int x) {
    bitset<32> b(x);
    return b.to_string();            
}

void tooctet(int x) {
    cout << oct << x;    
}

void tohex (int x) {
    cout << hex << x;
}

### II.1-i

void xorswap(int x, int y) {
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    cout << x << "  " << y;
}

### II.1-j

int length(int n) {
    int cnt = 0;
    while (n > 0) {
        n /= 2;
        cnt++;
    }
    return cnt;
}

double log2 (int x) {
    long double l = log(x);
    return l;
}

### II.1-k

int countsetbit (int x) {
    int cnt = 0;
    while (x > 0) {
        if (x & 1 == 1) {
            cnt++;
        }
        x >>= 1;
    }
    return cnt;
}

int countunsetbit (int x) {
        int cnt = 0;
    while (x > 0) {
        if (x & 1 == 0) {
            cnt++;
        }
        x >>= 1;
    }
    return cnt;
}

### II.1-l

int CountTrailingZero (int x) {
    int cnt = 0;
    while (x > 0) {
        if (x & 1 == 0) {
            cnt++;
            x >>= 1;
        }
        else {
            break;
        }
    }
    return cnt;
}

### II.1-m

int CountTrailingOne (int x) {
    int cnt = 0;
    while (x > 0) {
        if (x & 1 == 1) {
            cnt++;
            x >>= 1;
        }
        else {
            break;
        }
    }
    return cnt;
}

int CountLeadingZero (int x) {
    int cnt = 0;
    for (int i = 31; i >= 0; i--) {
        if (((x >> i) & 1) == 0) {
            cnt++;
        }
        else {
            break;
        }
    }
    return cnt;
}