shift (bitshift) through char array

[monkey_king]

Hi,
given a char(8bit's), I want to get the value of every 2bits,
so that a char will contain 4 values.
This is easily done with a shift left command (<<2).

As far as I understand,
char arrays are simply the different chars in consecutive order in the memory.
so essentially, I should be able to just shift2, through the entire array.

This is a short snippet that does want I want but not in the correct way.

int main(int argc, char *arg[]){
  unsigned char *chr = new unsigned char[8];
  for(int i=0;i<8;i++)
    chr[i] = 0x80 ;
  
  int i=0;
  unsigned char tmp;
  while(i<8){
    printf("11xx-xxxx bits of chr[%d]=%x\n",i,tmp&0xc0); //extract 1100 0000
    tmp = tmp<<2;
    printf("xx11-xxxx bits of chr[%d]=%x\n",i,tmp&0xc0); //extract 0011 0000
    tmp = tmp<<2;
    printf("xxxx-11xx bits of chr[%d]=%x\n",i,tmp&0xc0); //extract 0011 0000
    tmp = tmp<<2;
    printf("xx11-xx11 bits of chr[%d]=%x\n",i,tmp&0xc0); //extract 0011 0000
    i++;
  }

Basicly i would like to avoid doing 4 times 2 shift for each char.
and just do shift2 all the way through the array.
like

while(chararray not empty){
  print first 2 bits
  shift chararray 2 bits
}

thanks in advance

[cikara21]

#define NULL 0
....
while((tmp&0xc0) != NULL)
{
        printf("11xx-xxxx bits of chr[%d]=%x\n",i,tmp&0xc0); //extract 1100 0000    
        tmp = tmp<<2;
}

[Duoas]

In terms of how we humans view it, bits are treated the same way as we do any other number: most significant to least significant: 1010 binary Which reads as, left to right,
{1}\times{2^3} + {0}\times{2^2} + {1}\times{2^1} + {0}\times{2^0}

The shift operations assume this point of view. Hence, shift-left is "the same" as multiply by two, and shift-right is "the same" as divide by two. (There are some differences when it comes to overflow and storage, but ignore that for now.)

So 1010 binary << 2 becomes 101000 binary .
And 1010 binary >> 2 becomes 10 binary .

Now, the convenient thing is this multiply/divide relationship. Use a divide and a modulo to get every two digits out of every byte of the array:

#include <stdio.h>

int main()
  {
  unsigned char bits[] = { 0xAF, 0x57, 0x3C };
  /* bits = 10 10 11 11 01 01 01 11 00 11 11 00 */
  /* the bytes are ordered here MSB to LSB */

  int byte_index, pair_index, bit_index;
  unsigned char twobits;

  /* for every byte (MSB to LSB): */
  for (byte_index = 0; byte_index < 3; byte_index++)
    {
    /* for every bitpair (MS pair to LS pair) */
    for (pair_index = 3; pair_index >= 0; pair_index--)
      {
      /* get the two bits of interest */
      twobits = (bits[ byte_index ] >> (pair_index *2)) & 0x03;
      /* print them (msb to lsb) */
      for (bit_index = 1; bit_index >= 0; bit_index--)
        printf( "%1d", (twobits >> bit_index) & 1 );
      /* and a space */
      printf( " " );
      }
    }

  /* and also show the user what he should be seing */
  printf( " :output\n10 10 11 11 01 01 01 11 00 11 11 00 :what you should see\n" );
  return 0;
  }

As you can see, this can be done much more efficiently, but since you wanted two bits at a time I separated it into two inner loops.

Hope this helps.

[edit] Oh yeah, before I forget, this is the C++ forum. :)

[monkey_king]

Hi thanks for the replys.
@duoas
can you elaborate on why your code is more efficient?
and can you tell me why you choose to use %ld at line 22

[monkey_king]

Hi again,
thanks for the reply and the added info.

But I still fail to see why your code should be more efficient.

For each char i do 4 shift operations and 4 bitwise AND's, thats 8 bitwise operations.

For each char you do 4 shifts in the middle loop, futhermore you do 2 shifts for each passing of the inner loop. And you write youself, a multiplication of 2 means a shift by 1. So futhermore you do another shift in line19. That sums your program to 16 shift operations.

And concerning the bitwise AND's. You do 4 shifts in the middle loop, and 2 more in the inner most loop, that sums to 12 AND. And a total of 28 bitwise operations.

That is, if I'm not mistaken.

[vijayan121]

> i would like to avoid doing 4 times 2 shift for each char.
> For each char i do 4 shift operations and 4 bitwise AND's, thats 8 bitwise operations.

you can reduce it to just 4 AND operations by using 4 bit masks.

#include <iostream>
#include <limits>

int main()
{
  enum { char_bits = std::numeric_limits<unsigned char>::digits };
  struct _assert { char char_has_8_bits[ char_bits==8 ? +1 : -1 ] ; };

  enum { N = 8 } ;
  unsigned char* chr = new unsigned char[N];
  // initialize array

  const unsigned char mask[] = { 0xc0, 0x30, 0xc, 0x3 };
  for( int i=0 ; i<N ; ++i )
  {
    // unroll a loop here
    std::cout << (chr[i]&mask[0]) << '\n' << (chr[i]&mask[1]) << '\n'
              << (chr[i]&mask[2]) << '\n' << (chr[i]&mask[3]) << '\n' ;
  }
}

in this case, the value of the 2 msbs would be 192/128/64/0, the next two would be 48/32/16/0 and so on.
you can speed it up more by treating sizeof(unsigned long) chars (instead of a single char) as a unit for the mask operation. (in this case you need to take care while allocating the array to get it correctly aligned and the size rounded upwards if required)

[Duoas]

> can you elaborate on why your code is more efficient?
Sorry, my wording tripped you up. What I meant by that is that my code is not efficient, but it is descriptive.

> and can you tell me why you choose to use %1d at line 22
You want to see binary bit patterns, right? "00", "01", "10", and "11"? Neither printf() nor cout can print binary. What you would get is "00", "01", "02", and "03". So I just explicitly specify that I want to print one digit at a time.

You cannot avoid shifting once for each bit you want to display. That's eight shifts per byte. Fortunately, the overhead is very small for that. Here is the most efficient way you can get your output (without dropping down to x86 assembly):

#include <stdio.h>

char* to_binary( unsigned value, char* s, unsigned digitcount )
  {
  s[ digitcount ] = '\0';
  for (; digitcount > 0; value >>= 1)
    s[ --digitcount ] = (value &1) ? '1' : '0';
  return s;
  }

void print_bit_array( unsigned char bytes[], unsigned count )
  {
  unsigned byte_index;
  char     s[ 9 ];

  for (byte_index = 0; byte_index < count; byte_index++)
    {
    to_binary( bytes[ byte_index ], s, 8 );
    printf( "%s%.4s-%.4s", byte_index ? " " : "", s, s+4 );
    }
  }

int main()
  {
  unsigned char bits[] = { 0xAF, 0x57, 0x3C };
  /* bits = 1010-1111 0101-0111 0011-1100 */
  /* again, the bytes are ordered here MSB to LSB */
  /* and shown the way you want to see them */

  print_bit_array( bits, sizeof(bits)/sizeof(bits[0]) );

  printf( " :output\n1010-1111 0101-0111 0011-1100 :wanted\n" );
  return 0;
  }

Hope this helps.

[monkey_king]

...
you can reduce it to just 4 AND operations by using 4 bit masks.
...

That is correct I can get the 4 times 2 bit's by using bitmasks,
But I will still need to shift/div to get the integervalue.
Maybe I wasn't clear on my problem.

say the following 1byte pattern 0x9c
in binary: 1001 1100
then I would like to have the 4 times 2 bit integer represententation in this case

2-1-3-0

But thanks for your reply

[monkey_king]

.
.
.
Hope this helps.

It did, thanks for your help.