CODEWITHSUNDEEP
cbit-manipulation
ibg
ibg

Reputation: 161

Bitwise comparison

I have an array that represents an 8x8 "bit" block

unsigned char plane[8]

What I want to do is loop through this "bit" block horizontally and count up the number of times a change occurs between a 1 and 0.

When I extract a bit, it is getting stored in an unsigned char, so basically I want to increase a count when one char is nonzero and the other is zero.

What I have is the following:

int getComplexity(unsigned char *plane) {
    int x, y, count = 0;
    unsigned char bit;

    for(x = 0; x < 8; x++) {
        for(y = 0; y < 8; y++) {
            if(y == 0) {
                bit = plane[x] & 1 << y;
                continue;
            }

        /*
        MISSING CODE
        */
        }
    }
}

For the missing code, I could do:

if( (bit && !(plane[x] & 1 << y)) || (!bit && (plane[x] & 1 << y)) ) {
    bit = plane[x] & 1 << y;
    count++;
}

However, what I really want see is if there is some clever bitwise operation to do this step instead of having two separate tests.

Upvotes: 1

Views: 150

Answers (1)

Steve Cox
Steve Cox

Reputation: 2007

This is really just a gcc solution because the popcnt intrinsic wont work on every other compiler.

unsigned char plane[8];

static const uint64_t tmask = 0x8080808080808080UL;

uint64_t uplane = *(uint64_t *)plane; // pull the whole array into a single uint

return __builtin_popcnt( ~tmask & (uplane ^ (uplane >> 1) ) );

For x86 the popcnt instruction wasnt actually implemented until sse4.2 was (so rather recently). Also, although this looks like it relies on endianness, it doesn't because none of the individual bytes are allowed to interact thanks to the mask. It is making some assumptions about the way memory works :\

As a side note doing this same thing in the "horizontal" direction is just as easy:

return __builtin_popcnt(0xFFFFFFFFFFFFFFUL & ( uplane ^ (uplane >> 8) ) );

Upvotes: 2

Related Questions