Calculate parity bit from a string in C

Question

I am trying to calculate the parity bit in a string using the following code. I first calculate a parityByte for the string and then calculate a parityBit for that byte.

From what I have gathered, these functions should do the trick, but right now I'm not so sure. The program in which I use them fails, and I would like to know if it's because of these or if I should look some other place.

char calculateParity(char *payload, int size){
    char r = 0;
    int i;
    for(i = 0; i < size; i++){
        r ^= payload[i];
    }
    return calcParityBit(r);
}

char calcParityBit(char x){
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

Use `unsigned char`, not `char`. If you right-shift a (signed) `char` then the sign bit is preserved. This wrecks your parity calculation. Also, the line `x ^= x >> 8;` is unnecessary; `x` only has 8 bits. — r3mainer, Mar 31 '15 at 21:45
Can you give an example input that fails? I see nothing really wrong here (that useless `x ^= x >> 8` step does nothing even if `char` is signed and negative - flipping all bits does not change the parity) — harold, Apr 01 '15 at 13:26
An [answer to *How can I check if a value has even parity of bits or odd?*](https://stackoverflow.com/questions/21617970/how-can-i-check-if-a-value-has-even-parity-of-bits-or-odd/21618038#21618038) uses a similar method. — Peter Mortensen, Aug 26 '22 at 21:44

score 0 · Answer 1 · edited Aug 30 '22 at 00:58

0

As r3mainer comments: use unsigned char for the calculation. As char may be signed, the right shifting may replicate the sign bit.

Further, code typically runs best with a return value of int versus char. I recommend using a return value of int or even simply bool.

// Find parity (of any width up to the width of an unsigned)
int calcEvenParityBit(unsigned par, unsigned width) {
  while (width > 1) {
    par ^= par >> (width/2);  
    width -= width/2;
  }

  // Only return Least Significant Bit
  return par % 2;
}

int calculateEvenParity(char *payload, int size) {
  unsigned char r = 0;
  int i;
  for(i = 0; i < size; i++) {
    r ^= payload[i];
  }
  return calcEvenParityBit(r, CHAR_BIT);
}

Invert the result for odd parity.

edited Aug 30 '22 at 00:58

Peter Mortensen

30,738
21
105
131

answered Apr 01 '15 at 00:22

chux - Reinstate Monica

143,097
13
135
256

Looks like there is a `;` where a `{` should be. End of `int calcOddParityBit(unsigned par, unsigned width);` – David C. Rankin Apr 01 '15 at 00:52
@David C. Rankin Right you are – chux - Reinstate Monica Apr 01 '15 at 01:00
If I'm not mistaken, your probably also meant to return `par % 2` in `calcOddParityBit` `:p` – David C. Rankin Apr 01 '15 at 02:29
@David C. Rankin Right you are 2 – chux - Reinstate Monica Apr 01 '15 at 03:40
This maybe a nit, but the name of the function `calcOddParityBit` is not calculating the `OddParityBit`. Quite the opposite, it is calculating the ` `EvenParityBit`. For `odd` parity, if there are an `even` number of `1's` in `par`, then the `OddParityBit = 1` otherwise `OddParityBit = 0`. Try `calcOddParityBit` for `10 (1010)` & `11 (1011)`. For `10` it returns `0`, for `11` it returns `1`. (the `even` parity bit) `:p`. – David C. Rankin Apr 01 '15 at 04:40
@David C. Rankin Right you are #3. – chux - Reinstate Monica Apr 01 '15 at 13:42

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

With help from Bit Twiddling Hacks

char calcParityBit (unsigned char v)
{
    return (0x6996u >> ((v ^ (v >> 4)) & 0xf)) & 1;
}

This is 5 operations versus 7 (after taking @squeamish ossifrage's good advice).

edited May 23 '17 at 12:28

Community

1
1

answered Apr 01 '15 at 01:51

Doug Currie

40,708
1
95
119

Now you are going to have to change `v` to `x` `:p` Also, it is only calculating the parity bit for `even` parity. (e.g. odd number of `1's` parity bit is `1` for even parity) The opposite is true for `odd` parity. – David C. Rankin Apr 01 '15 at 04:33

score 0 · Answer 3 · answered Apr 10 '15 at 18:08

You must remember:

1) 'x >> a' the same thing for(int i = 0; i < a; i++) x/=2; because, if you use operator '>>' for SIGNED type, you duplicate first bit, whitch == 1 in signed types;

2) operators '>>' and '<<' returns unsigned int value;

(Error example: unsigned char y = (x << 2) >> 2; for reset (in 0) two first bits)

score -2 · Answer 4 · answered Apr 01 '15 at 00:36

Your function:

char calcParityBit(char x){
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

calculates parity for only three bits of your byte. To calculate parity of the entire 8 bits number, you can do something like this:

char calcParityBit(char x){
    return ( (x>>7) ^ 
             (x>>6) ^
             (x>>5) ^
             (x>>4) ^
             (x>>3) ^
             (x>>2) ^
             (x>>1) ^
             (x) ) & 1;
}

As you stick with the least significant bit, the fact that your argument is signed and the shift right operation may fill the shifted bits with '1' if the most significat bit was '1', is irrelevant for this solution (which is derived from yours)

Although it's good practice not to use number with sign if the sign is not of any actual use, and you treat the number as an unsigned one.

Calculate parity bit from a string in C

4 Answers4