bit operation

http://www.andrewwinter.com/programming/bitwise/

topCoder: A bit of fun: fun with bits

Set union

A | B

Set intersection

A & B

Set subtraction

A & ~B

Set negation

ALL_BITS ^ A

Set bit

A |= 1 << bit

Clear bit

A &= ~(1 << bit)

Negate bit

     A ^= (1 << bit)

Test bit

(A & 1 << bit) != 0

Programming Pearls: bitvector functions

const int SHIFT = 5;
const int MASK = (1<<SHIFT)-1;

inline void SET(unsigned int a[], int i) {
 a[i>>SHIFT] |= (1 << (i & MASK));
}
inline void CLEAR(unsigned int a[], int i) {
 a[i>>SHIFT] &= ~(1 << (i & MASK));
}
inline bool TEST(unsigned int a[], int i) {
 return a[i>> SHIFT] & (1 << (i & MASK));
}

int a[1 + N/(sizeof(int)<<3)];

上一贴BFS中用的visited最多支持到 2^27, int visited[2^27], 要用512M内存 (再多vc compilier Error C2148: total size of array must not exceed 0x7fffffff bytes --- 2GB) 。用上面这个bitvector数组可以只用 2^22 int, 16M memory，好很多了。相应改动非常少：

  int BFS( ... ) {
    // ...
    int N = 1 << (totalslots-1); // totalslots+4-5
    unsigned int *v = new unsigned int[N+1];
    memset(v, 0, sizeof(unsigned int)*(N+1));
    queue<State> Q;
    Q.push(State(status, 0, 0)
    SET(v, status); //v[status] = 1;
    while(!Q.empty()) {

                // ...
                // move to the next stump
                int ns = (s.status ^ (uid << totalslots)) | (next << totalslots);
                if(TEST(v, ns) == 0) { //if(v[ns] == 0)
                    SET(v, ns); //v[ns] = 1;
                }
                // ...

提交完这份用了bitvector array的代码后，在UVa 上显示运行时间0.000s :-)

Problem: UVa 594: One Little, Two Little, Three Little Endians

要注意的是，signed int是带着符号位移位的，所以我先把signed int 转成了 unsigned int

/*bit operation*/
#include "stdio.h"

short shift[4] = {24, 16, 8, 0};
int main() {
    int n;
    while(scanf("%d ", &n) != EOF) {    
        unsigned int d = 0;
        unsigned int m = n;
        for(int i = 0; i < 4; ++i) {
            d |= (m & 0xff) << shift[i];
            m = m >> 8; 
        }
        printf("%ld converts to %ld\n", n, d);
    }
}