Count bits in character and tally the bits

Question

This is only my 2nd programming class. There are 30 rooms, we have to see what is in each room and tally it. I already used the for loop to go through the 30 rooms and I know I have to use a bit counter to see what is in each room. I don't know how to count the bits in a word. Below are sample inputs/outputs and what I have so far in code.

Sample input:

9   23  @Z

If the key is:

0 gold_bar
1 silver_bar
2 diamond
3 copper_ring
4 jumpy_troll
5 air
6 angry_troll
7 plutonium_troll

And the line is 9 23 @Z then room at 9,23 (character Z with binary: 01011010) has items 1, 3, 4, 6. silver_bar, copper_ring, jumpy_troll, angry_troll

#include <stdio.h>
#include <stdlib.h>
int main()
{
// contains x and y coordinate
 int first, second;
  char third[100];
char Map[30][30];

// map initialization
for(int x=0; x<30; x++){
    for(int y=0; y<30; y++){
        Map[x][y] = '.';
    }
}


while(scanf("%d %d %s",&first, &second, third) != -1) {
    // Condition 1: a zero coordinate
    if (first==0 || second==0) exit(0);
    // Condition 2: coordinate out of range
    if (first<0 || first>30 || second<0 || second>30){
        printf("Error: out of range 0-30!\n");
        exit(1);
    }
// bit counter
    for( int bit_p=0; bit_p<8; bit_p++){

    }

    Map[second-1][first-1] = third[1];


return 0;
}

Sample input:

1   20  @@
2   21  @A
3   22  @#
4   23  @1
5   22  @@
6   22  @@
7   22  @@
8   22  @@
9   23  @Z  Here be trolls � not!
10  23  @+
12  23  @@
13  24  @@
11  22  @@
14  22  @2
15  21  @1
16  20  @@
17  19  @@
18  20  @@
19  19  @@
20  18  @@
21  17  @*
22  16  @*
23  15  @%
0   14  @7
0   gold_bar
1   silver_bar
2   diamond
3   copper_ring
4   jumpy_troll
5   air
6   angry_troll
7   plutonium_troll

Sample Output:

6   gold_bar
6   silver_bar
1   diamond
4   copper_ring
4   jumpy_troll
8   air
15  angry_troll
0   plutonium_troll

possible duplicate of [How to count the number of set bits in a 32-bit integer?](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer) — too honest for this site, Aug 25 '15 at 23:31
@Matthieu: If it is really just about counting if a specific bit is set, OP really should have done research on her own. — too honest for this site, Aug 26 '15 at 12:44

thurizas · Answer 1 · 2015-08-26T03:30:39.687

The individual bits of a word are not directly accessible with C, so we have to do other things to get at them.

Consider your values, which give which bit is set:

0 gold_bar          00000001B  or 0x01
1 silver_bar        00000010B  or 0x02
2 diamond           00000100B  or 0x04
3 copper_ring       00001000B  or 0x08
4 jumpy_troll       00010000B  or 0x10
5 air               00100000B  or 0x20
6 angry_troll       01000000B  or 0x40
7 plutonium_troll   10000000B  or 0x80

So with observation, lets consider what will happen if we have the following:

unsigned char test = 'z'
unsigned char res = test & 0x02

Now as you stated 'z' has a binary representation of 01111010 and if we do a logical and with 2 we have:

     z: 01111010B
  0x02: 00000010B
        ----------
        00000010B

So the expression test & 0x02 evaluates to 0x02. So, how can we use this? We can write something like:

     if((test & 0x02) == 0x02)
         ++cntSilverBars;

Extending this we have, assuming we have appropriately defined variables (i.e cntAuBars would be declared as int cntAuBars and hold the number of gold bars discovered:

     if((test & 0x01) == 0x01)
         ++cntAuBars;
     if((test & 0x02) == 0x02)
         ++cntAgBars;
     if((test & 0x04) == 0x04)
         ++cntDiamonds;
     if((test & 0x08) == 0x08)
         ++cntCuRings;
     if((test & 0x10) == 0x10)
         ++cntJumpyTroll;
     if((test & 0x20) == 0x20)
         ++cntSilverBars;
     if((test & 0x40) == 0x40)
         ++cntAir;
     if((test & 0x80) == 0x80)
         ++cntPuTroll;

While the above will work, it can be re-written as:

int itemCnt[8] = {0};         // array to hold count of items, index is item type
unsigned char test;           // holds contents of room.
int loc;
for(loc = 0; loc < 8; loc++)  // loop over every bit and see if it is set
{
     unsigned char bitPos = 1 << loc;  // generate a bit-mask 
     if((test & bitPos) == bitPos)
          ++itemCnt[loc];
}

For example, the following program:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
  unsigned char test = 'z';
  int           items[8] = {0};
  int           loc;
  int           ndx;

  for(loc = 0; loc < 8; loc++)
  {
      unsigned bitPos = 1 << loc;
      if((test & bitPos) ==  bitPos)
          ++items[loc];
  }


  for(ndx = 0; ndx < 8; ndx++)
  {
     printf("%d, ", items[ndx]);
  }

  return 0;
}

can be compiled as: gcc -g -ansi -pedantic -Wall temp.c -o temp, and when run produces the following array (when view in a debugger):

(gdb) print /t 'z'
$7 = 1111010
(gdb) print items
$8 = {0, 1, 0, 1, 1, 1, 1, 0}

thanks! how do i output the data so it's 6 gold_bar 6 silver_bar 1 diamond 4 copper_ring 4 jumpy_troll 8 air 15 angry_troll 0 plutonium_troll? Do I need to declare the variables? — janny, Aug 25 '15 at 23:19
@janny the array keeps track of things. The number of gold bars will be contained in the first element of the array (*i.e.* items[0]) just make sure the item array is declared outside of the loops that iterate over the rooms — thurizas, Aug 25 '15 at 23:24
I'm probably doing something wrong, I wrote printf("%d", itemCnt[0]); and the output is just 00000000000000000000000 — janny, Aug 26 '15 at 00:23
@janny added code to show how to print out the array. Also noticed I had a mistake in the loop (which I fix) — thurizas, Aug 26 '15 at 03:31

score 1 · Answer 2 · answered Aug 25 '15 at 23:12

This code examines a character and fills an array of 8 ints with value 0 if the bit at that position is 0 and value 1 if the bit at that position is 1

char c = 'Z';
int bits[8];
int n;
char aux = c;
for ( n=0; n<8; ++n ) {
  if ( aux & '\1' )
    bits[n] = 1;
  else
    bits[n] = 0;
  aux = aux >> 1;
}

aux & '\1' and aux = aux >> 1 are the heard of the code.

'\1' is the character with ASCII code 1 thus its bit at position 0 is 1 and all other bits are 0. When we do a bitwise AND of '\1' with a character we get 1 if that character a 1 at bit position 0 and we get a 0 otherwise.

aux = aux >> 1 will shift bits one position to the left so that in the next operation the bit at postion 0 will be the one which was originally at position 1.

score 0 · Answer 3 · answered Aug 25 '15 at 23:12

There's no built-in function for accumulating bit counts in a word. For each room, you'll need to check each of the 8 bits and, if that bit is set, increment the appropriate counting variable. There are many ways to do this, but especially for a class you want to do it as clearly as possible.

The basic idea is that you want to compare the word you read in ("third", in your framework) to a single bit mask shifted up to the bit position you're testing. Do the comparison by and'ing the mask against the input in and testing it using if statement. I've dropped a sample into your framework:

// bit counter
for( int bit_p=0; bit_p<8; bit_p++){
    if (third & (1 << bit_p))
        tally[bit_p]++;
}

The common piece is the structure if (input & MASK) {do_whatever}. Once you understand why that structure works, you can apply it to many situations.

Count bits in character and tally the bits

3 Answers3