{"id":1268,"date":"2020-05-28T20:25:33","date_gmt":"2020-05-29T03:25:33","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1268"},"modified":"2021-01-27T20:57:50","modified_gmt":"2021-01-28T04:57:50","slug":"bit-manipulation-tricks","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/05\/28\/bit-manipulation-tricks\/","title":{"rendered":"Bit Manipulation Tricks"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

Bit manipulation is all about tricks. bitset<\/code> is also a common data structure in set problems. <\/p>\n\n\n\n

Details<\/h2>\n\n\n\n

Bitwise Not<\/h4>\n\n\n\n
unsigned char ch = 2;\nstd::bitset<8> bs(~ch);\n\/\/ 11111101\nstd::cout << bs << std::endl;<\/code><\/pre>\n\n\n\n
Flip Last Set Bit<\/h4>\n\n\n\n
The last set bit is the rightmost set bit. i&(i-1)<\/code> does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT). <\/p>\n\n\n\n
(i-1)<\/code> \u00a0flips all the bits to the right of rightmost 1 in x and also including the rightmost 1. <\/p>\n\n\n\n
Power of Two<\/h4>\n\n\n\n
i&(i-1)==0 => power_2<\/code> can also be used to judge if a number is a power of two in O(1) time.<\/p>\n\n\n\n
Last Set Bit<\/h4>\n\n\n\n
i^(i&(i-1))<\/code> should work since i&(i-1)<\/code> flips only the last set bit. <\/p>\n\n\n\n
i&(-i)<\/code> also works. Since (-i)<\/code> is the two\u2019s complement (one\u2019s complement of i<\/code> plus 1) of i<\/code>. <\/p>\n\n\n\n
Iterate Subset<\/h4>\n\n\n\n
Given set S<\/code>, the following code traverse all the subset in S<\/code> in O(2^|S|)<\/code> time. See this post<\/a> in cp-algorithms.<\/p>\n\n\n\n
for (int j = s; j > 0; j = (j - 1) & s) {\n    printf(\"%04x\\n\", j);\n}<\/code><\/pre>\n\n\n\n
An important conclusion in the post is that the following nested loops will have O(3^n)<\/code> complexity.<\/p>\n\n\n\n
for (int m=0; m<(1<<n); ++m)\n    for (int s=m; s; s=(s-1)&m)<\/code><\/pre>\n\n\n\n
Belong To<\/h4>\n\n\n\n
To check if bit set of a<\/code> belongs it of b<\/code>, we could use (a&b)==a<\/code>.<\/p>\n\n\n\n
Bits Shift<\/h4>\n\n\n\n
Never shift negative numbers. Never shift negative number of bits. <\/p>\n\n\n\n
“For negative a<\/code>, the behavior of a << b<\/code> is undefined. “<\/p>\n\n\n\n
“For negative a<\/code>, the value of a >> b<\/code> is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).”<\/p>\n\n\n\n
“In any case, if the value of the right operand is negative or is greater or equal to the number of bits in the promoted left operand, the behavior is undefined.”<\/p>\n","protected":false},"excerpt":{"rendered":"
Summary Bit manipulation is all about tricks. bitset is also a common data structure in set problems. Details Bitwise Not Flip Last Set Bit The last set bit is the rightmost set bit. i&(i-1) does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT). (i-1) \u00a0flips all the bits…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,53],"tags":[],"class_list":["post-1268","post","type-post","status-publish","format-standard","hentry","category-alg","category-bit-manipulation"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1268","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1268"}],"version-history":[{"count":11,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1268\/revisions"}],"predecessor-version":[{"id":1565,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1268\/revisions\/1565"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1268"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}