Bit manipulation

AARRRGH

Hello

I've worked with bit manipulation in the past, but I now have a new challenge...

I am performing "binary polynomial" multiplication and division. To do this you represent polynomials as binary.

X^5 + 1 becomes 000100001
X becomes 00000010
X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1 becomes 11111111

As you can see, if the power is there, you use as 1, otherwise you use a 0.

I have to multiply and divide binary polynomials. I know how to do this. The problem is I don't know how big my polynomials are going to be. I have to be able to handle their size on the fly.

For example, I might be dividing 0000101011111001 by 1111

At the moment I am using bytes (unsigned chars) to try to keep track of everything. This is very messy as frequently my polynomials don't fit into a bytes "8 bit" shape. For example, 1111 doesn't fit into 8 bits too well.

Having to first figure out how many bits I am using, and then keep track of the extra unwanted bits in the byte... nightmare.

I've been working on this for two weeks and it is doing my head in.

Have any of you performed binary polynomial multiplication or division before? Do you have any suggestions for me?

I don't think I can use structs as they are limited to the size of an integer, and "bit sets" seem really complicated.

I am using C.

Any advice greatly appreciated.

Thanks

stevenmu

Did something like this back in college. IIRC we used multiple bytes to represent each value and wrote logic to carry a 1 from one byte to the next where neccessary.

I think we were explicitly told to do it that way, so it may have just been for practice and may not actually be the best way.

edit: not sure I explained that very well, an example is probably better, say we had two values to add 11111111 and 10000000. For each value we would use two bytes so the first value would be
00000000 and 11111111
the second would be
00000000 and 10000000
to add them we wrote the logic to loop through each bit (right to left), adding the values and carrying the 1, when we got to the last bit if there was a 1 to carry we would move it to the rightmost bit in the next byte, so in this case adding the above values gave
00000001 and 01111111
which equates to
0000000101111111

ianhobo

Hey,
What do you mean by:

At the moment I am using bytes (unsigned chars) to try to keep track of everything

Why can't you just use an unsigned int?
(Am I missing something? I mightn't be thinking inside the polynomial box here, so sorry.....)
The unsigned char of 1 is : 00000001b
And the unsigned int of 1 is : 00000000 00000000 00000000 00000001b

Using your example polynomials:
1) As an unsigned char

X^5 + 1 becomes 00100001
X becomes 00000010
X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1 becomes 11111111

2) As an unsigned int

X^5 + 1 becomes 00000000 00000000 00000000 00100001
X becomes 00000000 00000000 00000000 00000010
X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1 becomes
00000000 00000000 00000000 11111111

Will that not work?

For example, 1111 doesn't fit into 8 bits too well.

What do yo mean here? Using your previous examples, is 1111 simply not 00001111b?
(Or do you mean x^1111?)

I don't think I can use structs as they are limited to the size of an integer, and "bit sets" seem really complicated.

No, (I think) you can generally use any type you want in the bit field of a structure, char, int, double, but the limitations are that struct bit fields are compiler dependant - in terms of significant bit ordering so code portability is then questionable. Also, different compilers may byte align the structures differently.

Unless you need to use specific bit lengths every time, bit fields may not be the right thing to use anyway

Hope that helps