Numbers System:
- Decimal (base 10) : 123 = 1*10^0 + 2*10^1 + 3*10^2
- Binary (base 2)
- Hexadecimal (base16)
- Octal (base 8)
To get the digits/bits:
-Dicimal: 12 -> 12%10, 12/10 -> ....
-Binary: 8 -> 8%2, 8/2 -> .....
Binary Representation:
2^3 2^2 2^1 2^0
8 4 2 1
Common logic operations (with examples):
& and
| or
^ xor
! not
~ 1’s complement
>> shift right
5 (101) >> 1 = 2 // the first right 1 was lost
x >> n = x / (2 ^ n)
<< shift left
5 (00101)<< 2 = 20 (10100)
x << n = x * (2 ^ n)
if(x % 2 == 0) equl if((x & 1) == 0) // but take care of ()
Tricks:
a^b=c
a^c=b
c^b=a
So you can do partial xor:
for(int i = 1; i <= n; ++i) xor[i] = a[i] ^ xor[i - 1];
xor[l, r] = xor[r] ^ xor[l - 1];
operations on bits:
// Everything is 0 based counted from the right
/* to know the bit in an index */
int x, idx; cin>>x>>idx;
cout<<((x >> idx) & 1);
/* to Set a bit (make it 1) */
x |= (1 << idx);
/* to Reset a bit (make it 0) */
x &= ~(1 << idx);
/* to change a bit (0 -> 1 & 1 -> 0) */
x ^= (1 << idx);
/* check if num is power of 2 */
if(x & (x - 1) == 0)
/* 1 when power of 2 becouse
8 -> 1000
7 -> 0111
*/
/* to count the bits */
cout<<(int)log2(x) + 1;
/* built in fuctions */
bitset<10> b(5); // 10 is the size
cout<<b<<'\n'; // print 0000000101
b[0] = 0;
cout<<b<<'\n'; // print 0000000100
b.set();
cout<<b<<'\n'; // print 1111111111
b.flip(); //reverse all bits
cout<<b<<'\n'; // print 0000000000
b.flip(2);
cout<<b<<'\n'; // print 0000000100
/* Counting number of 1 s*/
cout<<b.count(); // count the 1 s
// if the number is represented in Decimal
__builtin_popcount(n); // take unsigned int O(1)
__builtin_popcountll(n); // take unsigned long long
__builtin_clz(n);
__builtin_clzll(n);
cout<<b.any(); // return 1 if there is one or more bits = 1
cout<<b.none(); // returen 1 if there isn't any bit = 1
1ll<<n // ll for long long and it equvilant to 2 power n
/* lowbit */
(n & -n) // -n is 2's compelement
if((n&1) == 0) // even take care of ()
https://en.cppreference.com/w/cpp/language/operator_precedence
Prefix with ( and, or) in range
int a[] = {0, 5, 10, 4, 4, 12, 70};
int a[] = {0, 5, 10, 4, 32, 64, 70};
int l = 3, r = 5;
int ans = -1; int l = 3, r = 5;
for(int i = l; i <= r; ++i) int ans = 0;
ans &= a[i]; for(int i = l; i <= r; ++i)
ans |= a[i];
int pre[10][32]{};
for(int i = 1; i <= 6; ++i){ int pre[10][32]{};
for(int j = 0; j < 32; ++j){ for(int i = 1; i <= 6; ++i){
if(a[i]&(1<<j)) for(int j = 0; j < 32; ++j){
pre[i][j] = 1; if(a[i]&(1<<j))
} pre[i][j] = 1;
} }
}
for(int i = 1; i <= 6; ++i)
for(int j = 0; j < 32; ++j) for(int i = 1; i <= 6; ++i)
pre[i][j] += pre[i - 1][j]; for(int j = 0; j < 32; ++j)
pre[i][j] += pre[i - 1][j];
int res = 0;
for(int j = 0; j < 32; ++j) int res = 0;
if(pre[r][j] - pre[l - 1][j] == r-l+1) for(int j = 0; j < 32; ++j)
res |= (1<<j); if(pre[r][j] - pre[l - 1][j])
res |= (1<<j);
cout<<ans<<' '<<res;
cout<<ans<<' '<<res;
problem
https://cses.fi/problemset/task/1623
Compelete Search
/* generate all subsets */
int n; cin>>n;
string s; cin>>s;
vector<string> v;
for(int mask = 0; mask < (1 << n); ++mask){
string tmp = "";
for(int i = 0; i < n; ++i){
if(mask & (1<<i))
tmp += s[i];
}
v.push_back(tmp);
}
for(auto it : v) cout<<it<<'\n';
Gold Trick
1000 is bigger than 0111
