Is there a more optimal way to approach some of these bitwise functions?

Question

I completed some bit manipulation exercises out of a textbook recently and have grasped onto some of the core ideas behind manipulating bits firmly. My main concern with making this post is for optimizations to my current code. I get the hunch that there are some functions that I could approach better. Do you have any recommendations for the following code?

#include <stdio.h>
#include "funcs.h"

// basically sizeof(int) using bit manipulation
unsigned int int_size(){
    int size = 0;
    for(unsigned int i = ~00u; i > 0; i >>= 1, size++);
    return size;
}

// get a bit at a specific nth index
// index starts with 0 on the most significant bit
unsigned int bit_get(unsigned int data, unsigned int n){
    return (data >> (int_size() - n - 1)) & 1;
}

// set a bit at a specific nth index
// index starts with 0 on the most significant bit
unsigned int bit_set(unsigned int data, unsigned int n){
    return data | (1 << (int_size() - n - 1));
}

// gets the bit width of the data (<32)
unsigned int bit_width(unsigned int data){
    int width = int_size();
    for(; width > 0; width--)
        if((data & (1 << width)) != 0)
            break;
    return width + 1;
}

// print the data contained in an unsigned int
void print_data(unsigned int data){
    printf("%016X = ",data);
    for(int i = 0; i < int_size(); i++)
        printf("%X",bit_get(data,i));
    putchar('\n');
}

// search for pattern in source (where pattern is n wide)
unsigned int bitpat_search(unsigned int source, unsigned int pattern,
        unsigned int n){
    int right = int_size() - n;
    unsigned int mask = 0;
    for(int i = 0; i < n; i++)
        mask |= 1 << i;
    for(int i = 0; i < right; i++)
        if(((source & (mask << (right - i))) >> (right - i) ^ pattern) == 0)
            return i - bit_width(source);
    return -1;
}

// extract {count} bits from data starting at {start}
unsigned int bitpat_get(unsigned int data, int start, int count){
    if(start < 0 || count < 0 || int_size() <= start || int_size() <= count || bit_width(data) != count)
        return -1;
    unsigned int mask = 1;
    for(int i = 0; i < count; i++)
        mask |= 1 << i;
    mask <<= int_size() - start - count;
    return (data & mask) >> (int_size() - start - count);
}

// set {count} bits (basically width of {replace}) in {*data} starting at {start}
void bitpat_set(unsigned int *data, unsigned int replace, int start, int count){
    if(start < 0 || count < 0 || int_size() <= start || int_size() <= count || bit_width(replace) != count)
        return;
    unsigned int mask = 1;
    for(int i = 0; i < count; i++)
        mask |= 1 << i;
    *data = ((*data | (mask << (int_size() - start - count))) & ~(mask << (int_size() - start - count))) | (replace << (int_size() - start - count));
}

Answer 1

The comment \\ basically sizeof(int) using bit manipulation is wrong. sizeof(int) gives the number of bytes (technically, "storage units"), but your function gives the number of bits.

If you change the name of the function to something descriptive like bits_in_int(), you might not need the comment.

The C language says that a char must always be a storage unit. If you know how many bits are in a char, you can just multiply by sizeof(int) to get the number of bits in an int. And there's a constant, CHAR_BIT, in header <limits.h> which is the number of bits in a character. So your whole int_size() function could be reduced to the compile-time expression sizeof(int) * CHAR_BIT;

If you really want to figure it out yourself, instead of using language-defined tools, your function could still use better style. First, a for loop shouldn't try to put everything in the loop header. The header should concern itself with the iteration. Everything else should either go before the loop, or in the loop body. I would replace your loop with:

for (unsigned int i = ~0u; i > 0; i >>= 1)
{
    size++;
}

size has nothing to do with controlling the loop, so I moved it to the body. I changed ~00u to ~0u. I see no reason to use an octal zero (00) instead of a decimal zero (0).

(Incidentally, I suggest never writing a single-statement loop or if statement without the braces. The typing you save doesn't make up for the increased risk of introducing an error in the future.)

This loop:

for(int i = 0; i < int_size(); i++)
     printf("%X",bit_get(data,i));

is inefficient. You're computing int_size() each time through the loop. This is better:

const unsigned int size = int_size();
for(int i = 0; i < size; i++)
{
    printf("%X",bit_get(data,i));
}

(You're calling int_size() more than once in other functions; I won't keep mentioning it.)

Get in the habit of declaring things const whenever possible. It makes the code clearer to the reader. It sometimes helps the compiler do a better job optimizing. And it makes you more aware of stuff that you can move out of loop bodies.

If a function returns an unsigned int, it probably doesn't make sense to return -1 to mean "invalid input" (function bitpat_get) or "not found" (function bitpat_search). -1 converts to an unsigned int filled with 1 bits (at least on a two's complement machine). This is probably a valid result for some input, so the calling code can't reliably extract the meaning from the return value.

Does bitpat_search() behave reasonably if the caller lies? What if the value passed in n is wrong for the given pattern? If the caller is supposed to do n = bit_width(source), why not do the calculation inside bitpat_search() instead of making the caller pass n?

Answer 2

Apart from GraniteRobert wrote, last 3 functions contain the repeating piece of code:

unsigned int mask = 1;
for(int i = 0; i < count; i++)
    mask |= 1 << i;

The repetition is a strong indication that the code does something useful, and deserves a function of its own. Especially if a repeating piece is a loop (No Raw Loops rule). That said, mask calculation is suboptimal and a loop is not necessary:

mask = (1 << count) - 1;

produces exactly the same result.