Bitan78 Bitan78 - 16 days ago 3
C Question

Setting a single bit in a Bitset causes several bits being set

I'm a novice in C and on Stackoverflow. I have an issue while adding elements to a bitset representing the ASCII table. The chars I pass should set the bitset's bit corresponding to their value in decimal (a=97).

But they are also setting other bits that are char +/- 32*a. I mean "a" would set 97, but also 225, 193, 161, 129, 97, 65, 33, 1.

Why is the code doing this? Can anybody point me in the right direction?
Here's my code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct bitset {
unsigned *data;
int size_in_bits;
int size_in_words;
} bitset;

// create a new, empty bit vector set of 'size' items
struct bitset *new_bitset(int size) {
int word_bits = sizeof(unsigned) * 8;

struct bitset *result;
result = malloc(sizeof(struct bitset));
result->size_in_bits = size;

result->size_in_words = size / word_bits;
if (size % word_bits != 0) {
result->size_in_words++;
}

result->data = malloc(sizeof(unsigned) * result->size_in_words);
for (int i = 0; i < result->size_in_words; i++) {
result->data[i] = 0;
}
return result;
}

// check to see if an item is in the set
// returns 1 if in the set, 0 if not, and -1 if 'item' is out of bounds
int bitset_lookup(struct bitset *this, int item) {
if (item < 0 || item > this->size_in_bits) {
return -1;
}
if (*this->data & (1 << item)) {
return 1;
}
return 0;
}

// add an item, with number 'item' to the set
// (returns 0 if item is out of bounds, 1 otherwise)
// has no effect if the item is already in the set
int bitset_add(struct bitset *this, int item) {
if (item < this->size_in_bits) {
*this->data |= 1 << item;
return 1;
}
return 0;
}

int main() {
char str1 = "a";
struct bitset *src1;

src1 = new_bitset(256);

bitset_add(src1, str1);

for (int j = 0; j < src1->size_in_bits; j++) {
if (bitset_lookup(src1, j) == 1) {
int myChar = j;
printf("%d ", myChar);
} else
printf("0 ");
}
return 0;
}

Answer

There are some issues in your code:

  • You cannot set a bit in an array of unsigned in a single step, you must determine which element of the array to modify and which bit of that element.

  • You should not hard code 8 bit chars, use CHAR_BIT from <limits.h>

  • Use calloc() to allocate a block of memory initialized to all bits zero, it simplifies the code.

  • You define a global variable bitset. This variable is not used, maybe you meant to define a type?

Here is a corrected and simplified version:

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct bitset {
    unsigned *data;
    int size_in_bits;
    int size_in_words;
};

// create a new, empty bit vector set of 'size' items
struct bitset *new_bitset(int size) {
    int word_bits = sizeof(unsigned) * CHAR_BIT;
    struct bitset *result = malloc(sizeof(struct bitset));

    result->size_in_bits = size;
    result->size_in_words = (size + word_bits - 1) / word_bits;
    result->data = calloc(result->size_in_words, sizeof(unsigned));
    return result;
}

// check to see if an item is in the set
// returns 1 if in the set, 0 if not, and -1 if 'item' is out of bounds
int bitset_lookup(struct bitset *this, int item) {
    int word_bits = sizeof(unsigned) * CHAR_BIT;

    if (item < 0 || item >= this->size_in_bits) {
        return -1;
    }
    return (this->data[item / word_bits] >> (item % word_bits)) & 1;
}

// add an item, with number 'item' to the set
// (returns 0 if item is out of bounds, 1 otherwise)
// has no effect if the item is already in the set
int bitset_add(struct bitset *this, int item) {
    int word_bits = sizeof(unsigned) * CHAR_BIT;

    if (item >= 0 && item < this->size_in_bits) {
        this->data[item / word_bits] |= 1U << (item % word_bits);
        return 1;
    }
    return 0;
}

int main(void) {
    char str[] = "Hello world";  
    struct bitset *set = new_bitset(256);

    for (int i = 0; str[i] != '\0'; i++) {
        bitset_add(set, (unsigned char)str[i]);
    }

    for (int j = 0; j < set->size_in_bits; j++) {
        if (bitset_lookup(set, j) == 1) {
            printf("%c ", j);
        }
    }  
    printf("\n");
    return 0;
}