치카냥3, C (gcc)

치카냥3

// 치카냥

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

void print_bits(int width, int x, int newline) // 테스트용
{
    for (int i = width-1; i >= 0; i--) printf("%01d", x >> i&1);
    if (newline) puts(""); else printf(" ");
}

int bit_count_2bits(int x) // 2개씩 카운트
{
    int ret = 0;
    while (x > 0) { // 16번 수행
        ret = ret + (x & 0x03) - ((x & 0x03) >> 1);
        // 00 -> 00
        // 01 -> 01
        // 10 -> 01
        // 11 -> 10
        x = x >> 2;
        // loop unroll시 연산자 총 95개
    }
    return ret;
}

int bit_count_4bits(int x) // 4개씩 카운트
{
    int ret = 0;
    while (x > 0) { // 8번 수행
        x = x & ~0x0F | ((x & 0x0F) - ((x & 0x0A) >> 1));
        // 1101 -> 1001
        // 0101 -> 0101
        ret = ret + ((x & 0x03) + (x >> 2 & 0x03));
        x = x >> 4;
        // unroll시 연산자 총 103개
    }
    return ret;
}

int bit_count_8bits(int x) // 8개씩 카운트
{
    int ret = 0;
    x = x & ~0xFF | ((x & 0xFF) - ((x & 0xAA) >> 1));
    x = x & ~0xFF | ((x & 0x33) + (x >> 2 & 0x33));
    ret = ret + (x & 0x0F) + (x >> 4 & 0x0F);
    x = x >> 8;
    x = x & ~0xFF | ((x & 0xFF) - ((x & 0xAA) >> 1));
    x = x & ~0xFF | ((x & 0x33) + (x >> 2 & 0x33));
    ret = ret + (x & 0x0F) + (x >> 4 & 0x0F);
    x = x >> 8;
    x = x & ~0xFF | ((x & 0xFF) - ((x & 0xAA) >> 1));
    x = x & ~0xFF | ((x & 0x33) + (x >> 2 & 0x33));
    ret = ret + (x & 0x0F) + (x >> 4 & 0x0F);
    x = x >> 8;
    x = x - ((x & 0xAA) >> 1);
    x = (x & 0x33) + (x >> 2 & 0x33);
    ret = ret + (x & 0x0F) + (x >> 4 & 0x0F);
    // 연산자 72개
    return ret;
}

int bit_count_16bits(int x) // 16개씩 카운트
{
    int ret = 0;
    x = x & ~(0xFF << 8 | 0xFF) | ((x & (0xFF << 8 | 0xFF)) - ((x & (0xAA << 8 | 0xAA)) >> 1));
    x = x & ~(0xFF << 8 | 0xFF) | ((x & (0x33 << 8 | 0x33)) + (x >> 2 & (0x33 << 8 | 0x33)));
    ret = ((x & (0xFF << 8 | 0xFF)) + ((x & (0xFF << 8 | 0xFF)) >> 4)) & (0x0F << 8 | 0x0F);
    ret = (ret & 0x0F) + (ret >> 8 & 0x0F);
    x = x >> 16;
    x = x - ((x & (0xAA << 8 | 0xAA)) >> 1);
    x = (x & (0x33 << 8 | 0x33)) + (x >> 2 & (0x33 << 8 | 0x33));
    x = x + ((x >> 4) & (0x0F << 8 | 0x0F));
    ret = ret + (x & 0x0F) + (x >> 8 & 0x0F);
    // 연산자 65개
    return ret;
}

int bit_count(int x) {
    return bit_count_16bits(x);
}

int main()
{
    srand(time(NULL));
    for (int i = 0; i < 100; i++) {
        int number = (rand() & 0xFFFF) << 16 | (rand() & 0xFFFF);
        printf("%9d: %2d (should be %2d)\n", number, bit_count(number), __builtin_popcount(number));
        assert(bit_count(number) == __builtin_popcount(number));
    }
}


run \| edit \| history \| help	1