fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. // cơ sở để học dp bitmask, dp sos
  5. // duyệt trâu bằng bitmask 
  6.  
  7. // Cách 1: x & (1 << i) 
  8.  
  9. // giá trị trả về: 
  10. // trường hợp bit thứ i bật: trả về 2^i  
  11. // trường hợp bit thứ i tắt: trả về 0  
  12.  
  13. // idx	  5 4 3 2 1 0 
  14. // ------------------
  15. //   x = 1 0 1 0 0 1
  16. // &     0 1 1 1 1 1 
  17. //   ----------------
  18. //       0 0 1 0 0 1    
  19.  
  20. // Cách 2: (x >> i) & 1 
  21. // idx	  5 4 3 2 1 0 
  22. // ------------------
  23. //   x =         1 0 
  24. // &			   1
  25. //   ----------------
  26. //                 0
  27.  
  28. // giá trị trả về:  
  29. // trường hợp bit thứ i bật: trả về 1  
  30. // trường hợp bit thứ i tắt: trả về 0  
  31.  
  32. bool checkBit(int x, int i) {// để kiểm tra bit thứ i của x có bật hay không?
  33. 	return (x & (1 << i)); // Cách 1 
  34. 	return ((x >> i) & 1); // Cách 2 
  35. }
  36.  
  37. int turnOnBit(int x, int i) {// bật bit thứ i của x
  38. 	return (x | (1 << i)); 
  39. }
  40.  
  41. // 0 ^ 1 = 1 
  42. // 1 ^ 1 = 0 
  43. int flipBit(int x, int i) {// đảo bit thứ i của x 
  44. 	return (x ^ (1 << i)); 
  45. }
  46.  
  47. int turnOffBit(int x, int i) { // tắt bit thứ i của x 
  48. 	return (x & ~(1 << i));  
  49. }
  50.  
  51. // n = 5  
  52. // 1 0 1 0 0: {0, 2}  
  53. // 1 1 0 1 1: {0, 1, 3, 4}
  54.  
  55. // liệt kê tất cả tập con của một mảng có n phần tử  
  56. // n = 3  
  57. // 000 
  58. // 001
  59. // 010 
  60. // 011
  61. // 100
  62. // 101
  63. // 110
  64. // 111 = 7 = 2^3 - 1   
  65.  
  66. void backtrack(int n) {
  67. 	for (int msk = 0; msk < (1 << n); msk++) {
  68. 		for (int i = 0; i < n; i++) {
  69. 			if (checkBit(msk, i)) cout << i << ' '; 
  70. 		}
  71. 		cout << '\n'; 
  72. 	}
  73. }
  74.  
  75. // __builtin_popcount(x) // đếm số bit 1 của x, x = 1110001  (__builtin_popcountll(x) cho x kiểu long long)
  76. // __builtin_ctz(x) // đếm số bit 0 tận cùng của x counting trailing zeroes
  77. // __builtin_clz(x) // đếm số bit ở đầu của x 
  78.  
  79. // x = 110011000
  80. // __builtin_ctz(x) = 3  
  81.  
  82. // x & (-x) fenwick tree, BIT 
  83.  
  84. // lỗi tràn số: 
  85. // (1ll << i)
  86.  
  87.  
  88. // code tìm kiếm nhị phân, segment tree: 
  89. // int mid = (l + r) / 2; 
  90. // => int mid = (l + r) >> 1; 
  91. // an toàn cho trường hợp đoạn âm 
  92.  
  93. int main() {
  94. 	ios::sync_with_stdio(0); cin.tie(0); 
  95.  
  96. 	// &: and 
  97. 	// |: or
  98. 	// ^: xor 
  99. 	// ~: not  
  100. 	// <<: dịch trái  
  101. 	// >>: dịch phải  
  102.  
  103. 	// and  
  104. 	// 1 & 1 = 1  
  105. 	// 0 & 1 = 0    
  106. 	// 0 & 0 = 0   
  107.  
  108. 	// or  
  109. 	// 1 | 1 = 1  
  110. 	// 0 | 1 = 1  
  111. 	// 0 | 0 = 0   
  112.  
  113. 	// xor  
  114. 	// 1 ^ 1 = 0  
  115. 	// 0 ^ 1 = 1 
  116. 	// 0 ^ 0 = 0    
  117.  
  118. 	// // a = b <=> a ^ b = 0   
  119. 	// ~ 
  120. 	// ~1 = 0 
  121. 	// ~0 = 1   
  122.  
  123. 	// <<: phép dịch trái  
  124. 	// 1101 << 1 = 11010 (tương đương với nhân 2)
  125. 	// << i (tương đương với nhân 2^i)
  126.  
  127. 	// >>: phép dịch phải   
  128. 	// 1101 >> 1 = 110 (tương đương với / 2) 
  129. 	// >> i (tương đương với / 2^i)
  130.  
  131. 	cout << (1ll << 60) << '\n'; 
  132. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1152921504606846976
https://ideone.com/RZlxhU
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!