accessing every nth element in array (hamming code)

Question

So basically I'm creating a program that prompts the user to enter a character like 'A' and it returns their binary value according to the ASCII chart which in this case is 01000001. What should be outputted is a 12-bit hamming code sequence with 8 data bits and 4 parity bits. What I'm having trouble with is coming up with a way to insert the correct data bits into every array position that is basically not a power of 2. I should mention that the type of array is char.

So like it should print out: _ _ 0 _ 1 0 0 _ 0 0 0 1 with the blank spaces representing where the parity bits will go. Right now my code just prints out 000001000001 (without the parity values being determined so far) but I can't figure out a way to position each of the 8 data bits into a non-parity bit location.

I assumed I would have to edit my for loop which currently involves for(int i = 12; i >= 0; i--) but I can't seem to figure out a mathematical pattern I could use. I'm not sure if my current approach is possible either. Any hints or help would be appreciated.

Below is basically just a really rough outline of the part of code I'm struggling with:

for (int i=12; i>=0; i--) {
    if ((int)(n/pow(2,i)) > 0) {
        //index = 1
        n = n - pow(2,i);
    }
    else
        //index = 0
 }

Use the logical and operator to set specific bits to 0 (in a 4 bit integer for example, x &= 7 sets the fourth, index 3, to 0). — kabanus
Hi! I'm not really following how x &= 7 sets index 3 to 0? Why 7? — Nicepeach
@user3386109 is correct. You need a number with all ones, and a 0 where you want to clear. — kabanus

Gene Gene · Accepted Answer · 2019-10-04T04:49:10

The operations you'll need to become familiar with are mask and shift. Don't use pow for bit twiddling. It's a big, heavyweight function meant for numerical calculations.

There are a few ways to generate the _ _ 0 _ 1 0 0 _ 0 0 0 1 pattern you seek. One is to clear the rightmost space first. If x holds the original value 0100001, then the first step is to mask out all but the last 4 bits. This is x & 0xfu. The & is logical "and." All the other bits can be masked off with x & ~0xfu. The ~ is bitwise "not." Now you want to shift these other bits left one place and combine them with the low order 4 bits using "or". So in all we have:

unsigned x = 'A';
unsigned a = (x & 0xfu) | ((x & ~0xfu) << 1);

To move the topmost bit one to the left, follow the same procedure, only now you want the rightmost 8 bits to stay where they are, while the 9th and higher move one to the left. The mask you need is 0xffu. So we end up with

unsigned result = (a & 0xffu) | ((a & ~0xffu) << 1);

Now you can "or" in the parity bits and then print out the bitwise representation with something like:

for (unsigned m = 0x800; m; m >>= 1) printf("%d", (m & result) != 0);

Again the 0x800 is a mask for bit 11. You use it to inspect bit 11 of the result with (m & result) != 0. This has the value 1 if the corresponding bit of result is set, else 0, exactly what you want to print. Each successive iteration of the for loop shifts the mask one place to the right. The loop stops when the bit is shift completely out. This happens after 12 iterations, so you print 12 bits, which seems to be what you want.

Note I've used unsigned types throughout. This isn't strictly necessary here, but it's normally less error prone to use unsigned types for bit operations, since sign extension can cause unexpected results.

All in all, you can test this out with 0xff as the input to see the "holes" where the parity bits belong:

#include <stdio.h>
int main(void)
{
    unsigned x = 0xffu;
    unsigned a = (x & 0xfu) | ((x & ~0xfu) << 1);
    unsigned result = (a & 0xffu) | ((a & ~0xffu) << 1);
    for (unsigned m = 0x800; m; m >>= 1) 
      printf("%d", (m & result) != 0);
    return 0;
}

This prints 001011101111 as you'd hope and expect.

There are lots of interesting details to work out. I'll let that for you.

accessing every nth element in array (hamming code)

1 Answers