Bit vector implementation from a given array

Question

I'm trying to create a bit vector set from a given array. Not sure how to start it off. For example given the array: int rows[] = {1, 2, 5} I need to make a function unsigned short MakeBitVector(int values[], int nValues) You're allowed to assume that the range for the elements in the array is 1-9. Here's what I have so far:

unsigned short MakeBitVector(int values[], int nValues)
{
  (55)unsigned short int set = calloc(nValues, sizeof(unsigned short));
  for(int i = 0; i < nValues; i++){
    (57)set[i] = values[i];
  }
  return set;
}

I keep getting warnings and errors:

bits.c:55: warning: initialization makes integer from pointer without a cast

bits.c:57: error: subscripted value is neither array nor pointer

Any ideas on how to fix this?

Vlad · Accepted Answer · 2012-05-10 20:55:13Z

4

You definitely need your set to be a pointer:

unsigned short int* set = calloc(nValues, sizeof(unsigned short));

And you have to change the return type of the function to pointer as well.

Edit: if you want to pack everything into one int, you can go on in a simpler way:

unsigned short MakeBitVector(int values[], int nValues)
{
    unsigned short int set = 0;
    for (int i = 0; i < nValues; i++)
        set |= 1 << values[i];
    return set;
}

You don't need to allocate a single int, returning the copy is just fine.

edited May 10, 2012 at 20:55

answered May 10, 2012 at 20:42

Vlad

35.7k7 gold badges82 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

user1386132 Over a year ago

This works. but is there any way that I can allocate memory without having to change everything to a pointer.I don't want to have to change the return type to a pointer.

Mankarse Over a year ago

@Vlad: That was me -- A bit-vector is a set of values represented by a binary string (eg {1,2,5} is represented as 11001}. There is no need for dynamic allocation to make one of these (if the array is known to only contain elements in the range 1-9), and this answer taken on its own will end up with the rest of the code indexing into the set by a short at a time, rather than by a bit at a time.

Vlad Over a year ago

@Mankarse: I cannot guess the semantics of values, it might be the copy of the bit vector as well. For the bit vector, I would not stay at just one int, as this restricts the set capacity to max of 64. So the bit vector's underlying structure has to be a kind of array.

Mankarse Over a year ago

@Vlad: From the question "You're allowed to assume that the range for the elements in the array is 1-9". So restricting the capacity is not a problem.

Vlad Over a year ago

@user: well, what is your data layout? How do you plan to process more than 64 bits in the vector? Do you plan to hold the vector in one int, or in several?

|

Peter · Accepted Answer · 2012-05-10 20:56:48Z

2

I don't think you need dynamic allocation at all; calloc is just confusing things. Also, you will need to operate on single bits somewhere which your code isn't at present. What about this:

unsigned short MakeBitVector(int values[], int nValues) {
  unsigned short int set = 0;
  for(int i = 0; i < nValues; i++){
    set |= 1 << values[i];
  }
  return set;
}

Obviously the output of this is undefined if the input contains indices >= 16, but you said that shouldn't be a problem (and you could easily extend it to 32 anyway).

answered May 10, 2012 at 20:56

Peter

7,3552 gold badges37 silver badges46 bronze badges

Comments

Makoto · Accepted Answer · 2012-05-10 20:42:00Z

0

set isn't a pointer. Change that to a pointer instead. You would also need to return a pointer as well.

answered May 10, 2012 at 20:42

Makoto

107k29 gold badges199 silver badges236 bronze badges

Collectives™ on Stack Overflow

Bit vector implementation from a given array

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related