5.4-bitManipulation.cxx

/* 5.4
 * Explain what the following code does: ((n & (n-1)) == 0).
 */

#include <cmath>
#include <cstdio>
#include "assert.h"

void test5_4() {

    /*
     * dec          bin
     * --------------------------
     *
     * 0         ==     00000000b
     * 0-1       ==     11111111b
     * __________________________
     * 0&-1      ==     00000000b   -> (0==0) -> true
     *
     *
     * 1         ==     00000001b
     * 1-1       ==     00000000b
     * __________________________
     * 1&(1-1)   ==     00000000b   -> (0==0) -> true
     *
     *
     * 2         ==     00000010b
     * 2-1       ==     00000001b
     * __________________________
     * 2&(2-1)   ==     00000000b   -> (0==0) -> true
     *
     *
     * 3         ==     00000011b
     * 3-1       ==     00000010b
     * __________________________
     * 3&(3-1)   ==     00000010b   -> (2==0) -> false
     *
     *
     * 4         ==     00000100b
     * 4-1       ==     00000011b
     * __________________________
     * 4&(4-1)   ==     00000000b   -> (0==0) -> true
     *
     *
     * 5         ==     00000101b
     * 5-1       ==     00000100b
     * __________________________
     * 5&(5-1)   ==     00000100b   -> (4==0) -> false
     *
     *
     * 6         ==     00000110b
     * 6-1       ==     00000011b
     * __________________________
     * 6&(6-1)   ==     00000010b   -> (2==0) -> false
     *
     *
     * 7         ==     00000111b
     * 7-1       ==     00000110b
     * __________________________
     * 7&(7-1)   ==     00000110b   -> (6==0) -> false
     *
     *
     * 8         ==     00001000b
     * 8-1       ==     00000101b
     * __________________________
     * 8&(8-1)   ==     00000000b   -> (0==0) -> true
     *
     *
     * 9         ==     00001001b
     * 9-1       ==     00001000b
     * __________________________
     * 9&(9-1)   ==     00001000b   -> (8==0) -> false
     *
     *
     * 10        ==     00001010b
     * 10-1      ==     00001001b
     * __________________________
     * 10&(10-1) ==     00001000b   -> (8==0) -> false
     *
     * ------------------------------------------------
     *
     * n=0   ==   true
     * n=1   ==   true
     * n=2   ==   true
     * n=3   ==   false
     * n=4   ==   true
     * n=5   ==   false
     * n=6   ==   false
     * n=7   ==   false
     * n=8   ==   true
     * n=9   ==   false
     * n=10  ==   false
     *
     * true answers: 0,1,2,4,8
     *
     * it seems that (n & (n-1)) can be used to determine if
     * a number is a powers of 2.
     */

    for (size_t i = 0; i < 64; i++) {
        unsigned int n = pow(2, i);
        assert((n&(n-1)) == 0);
    }
    printf("5.4 passed!\n");
}