4
\$\begingroup\$

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));
}
\$\endgroup\$
3
  • \$\begingroup\$ Curious, why ~00 instead of ~0? \$\endgroup\$ Jun 21 '14 at 6:10
  • \$\begingroup\$ int_size() assumes the bit size of an int is the same as the bit size of unsigned. Certainly very common, but not required by the C spec. \$\endgroup\$ Jun 21 '14 at 6:17
  • \$\begingroup\$ ~0u, at the very least, is necessary, to ensure it's unsigned. I did ~00u because 00 makes it octal, but according to posts below, it seems that ~0u is fine for C99 standard. \$\endgroup\$ Jun 24 '14 at 22:02
6
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\begingroup\$ Note: 1) 0 is an octal 0. See 6.4.4.1 1. 2) Agree 00 is certainly an unorthodox style. \$\endgroup\$ Jun 21 '14 at 6:09
  • \$\begingroup\$ Suspect sizeof(int)*CHAR_BIT != int_size() should padding exist. Although I know of no machine since 2000 that uses padding in unsigned. \$\endgroup\$ Jun 21 '14 at 6:14
  • \$\begingroup\$ @chux: Thanks for the reminder that 0 is octal; I had forgotten that little detail of the grammar. And I think you are right about sizeof(int). An implementation doesn't have to use all the bits it allocates for an integer. I believe an implementation could have a 13-bit integer named int13_t with sizeof(int13_t) == 2. Weird, but legal. \$\endgroup\$ Jun 21 '14 at 14:45
  • \$\begingroup\$ bitpat_search() is being used to search for a bit pattern, so I'm not sure what a good return value would be if the caller lies. n is the width of pattern. I'm not sure why the exercise wanted this, you could just eliminate this parameter altogether, and I was confused as to why it was included. \$\endgroup\$ Jun 24 '14 at 11:51
1
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.