Need urgent help on my homework! Due day soon!

Hi all,

I'm programming an algorithm which needs to operate on bits. I know C/C++ has bitset class. But it is not enough for
me. Because I also need to do the operation with x(don't care) bit and we need to combine the bits together.

For example, let's use 3 to represent the don't-care bit. In case 1001 and 1000 are inputs which give same output,then
1001 and 1000 can be combined into 1003. And Similarly 1003 and 0003 can be combined into 3003.
But 1003 and 1101 can not be combined.

I also need bitwise operation such like the number of 1's.

How can I implement this class? Is there a fast way by just inheriting the behavior of <bitset> class?
Or do you suggest implementing the class from scratch?

Thanks!

the problem you described doesn't make any sense to me -

And Similarly 1003 and 0003 can be combined into 3003.
But 1003 and 1101 can not be combined.

why? what is the difference?

However, it sounds like you need bit masks and all your problems will be gone (haha).

I don't get the combining either, and if 1000 and 1001 are binary (I assume), what is 1003?

Sorry for the confusing part.
For example, for a boolean function, there are 4 inputs ABCD, one output K;
if for both the input patterns 1000 and 1001, the output is 1.
Then we say we 'dont care' the D value. Thus, we combine the above two input as a single input: 1003;
Here 3 represent the "dont care" bit.

And similarly we can combine the inputs with "don't care" bit:
if for both the input pattern 1003 and 0003, the output is 1. In this case, only the first bit A is different.
Then we can combine them together into 3003.

Quote:

---

Originally Posted by GCDEF

I don't get the combining either, and if 1000 and 1001 are binary (I assume), what is 1003?

---

3 just represent the bit that could be either 1 or 0. We just don't care this bit because either choice will yield the same output result.

we use the term bit masks. google it if you dont know what I mean.

Quote:

---

Originally Posted by ertss

Thus, we combine the above two input as a single input: 1003;

---

I'm sorry, that sill makes no sense to me. How does 1000 and 1001 make 1003 and how does a bit hold the value 3?

Quote:

---

Originally Posted by ertss

How can I implement this class? Is there a fast way by just inheriting the behavior of <bitset> class?

---

I don't know the exact requirements but maybe you could use two bitsets to implement the class you require. One bitset is used to represent an ordinary bit set and the other is used to mark care/don't care bits.

Hi, ertss, we are not really following you here, except for the part where 3 represents the bit the value of which is not important. (Why 3, BTW, why not some symbol, like d for "don't care"?)

Anyway, let me see if I can help you explain it better: You say that the values somehow combine. What exactly you mean by "combine"? From what I can see, it seems that you're using the "combined" form to represent both inputs at once (or rather a set of inputs that match a certain pattern, with the exception of "dont-care" bit positions). Is this correct? (If so, what nuzzle suggested seems like a way to go.)

You also talk about outputs. You need to tell us what these outputs are (what they represent) and what are the rules to get them.

Finally, since this is an assignment, why don't you post the actual text of it? Maybe it explains it better.

TheGreatCthulhu, thanks for helping me to explain this. Yes, i am using the "combined" form to represent
both input at once such that this could be used in the next steps of the alogorithm.

Basically the homework is implementing Quine–McCluskey algorithm, which is a algorithm to minimize logic function.

I used '3' to just explain the problem im dealing with. And I was thinking of making a new class inheriting the bitset class and it also should be able to deal with bit-string with "don't care" or "3" bit.

Now I think I should create a new class without inheritance by representing the bits in terms of string.

I think I have figured it out. Thank you and sorry for the inexplicit wording.

Quote:

---

Originally Posted by TheGreatCthulhu

we are not really following you here,

---

The OP is just recapitulating the meaning of don't care with two examples:

1. If 1001 and 1000 both give the same output (after having passed a logical circuit of some sort)the rightmost bit is a don't care (so these two inputs give the same output as 1003 would).

2. And if the inputs 1003 and 0003 give the same output then the leftmost bit is don't care (so these two inputs give the same output as 3003 would).

Quote:

---

Originally Posted by ertss

Now I think I should create a new class without inheritance by representing the bits in terms of string.

---

Resorting to string on every posssible occasion is a very BASIC-ish habit I suggest you kick as soon as possible in C++.

Why not use a bitset as you initially had in mind and another bitset as I suggested to represent the care/don't care extension?

Generally you should never inherit from STL data structures. It's a no-no because STL isn't OO.

You'll have to develop your own class anyway but using two bitsets most probably will be more elegant and efficient than a string in the implementation so that's what I would suggest.

Thanks nuzzle, I will give the two bitset way some thoughts.

If I understood it correctly, are you saying creating a new class object which include two bitset to represent the bits?

For example:

Code:

---

class Two_bitset_representation{
public:
  bitset bits;
  bitset mask;

  ...
  ...
};

---

Quote:

---

Originally Posted by ertss

For example:

---

Not quite. It's more like this.

Code:

---

class Bitset_with_dontcare {
public:
  // usage interface

private:
  bitset bits;
  bitset mask;
};

---