ch2-Bitwise Operators

Chapter_2     ch2-Strings                                                             ch2-Conditionals 

Contents:

getbits.c     ch2-bitstrings  (bitstrings.c,  BitStrings.cpp)     Exercise_2-6     Exercise_2-7     Exercise_2-8     bitcount.c     Exercise_2-9

getbits.c     K&R, p. 49     (get last bits of integer starting at specified position)     download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// get the last n bits from x starting at position p:

unsigned getbits(unsigned x, int p, int n);

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits[LENGTH];

  unsigned x;

  int len, p, n, diff;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  len = bitstring(bits, x);

  printf("%s\n", bits);

  printf("Return last 0 <= n <= %d bits ", len);

  printf("starting at position max(0, n-1) <= p <=%d:\n", len-1);

  printf ("n = ");

  scanf("%d", &n);

  printf ("p = ");

  scanf("%d", &p);

  x = getbits(x,p,n);

  len = bitstring(bits,x);

  diff = n - len;

  while (diff > 0)

  {

    putchar('0');

    diff--;

  }

  printf("%s\n", bits);

  return 0;

}

// get the last n bits from x starting at position p:

unsigned getbits(unsigned x, int p, int n)

{

  return (x >> (p+1-n)) & ~(~0 << n);

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc getbits.c -o getbits

./getbits

Give a positive integer: 74

1001010

Return last 0 <= n <= 7 bits starting at position max(0, n-1) <= p <=6:

n = 3

p = 4

010

./getbits

Give a positive integer: 74

1001010

Return last 0 <= n <= 7 bits starting at position max(0, n-1) <= p <=6:

n = 3

p = 5

001

./getbits

Give a positive integer: 97

1100001

Return last 0 <= n <= 7 bits starting at position max(0, n-1) <= p <=6:

n = 3

p = 4

000

./getbits

Give a positive integer: 97

1100001

Return last 0 <= n <= 7 bits starting at position max(0, n-1) <= p <=6:

n = 4

p = 3

0001

./getbits

Give a positive integer: 97

1100001

Return last 0 <= n <= 7 bits starting at position max(0, n-1) <= p <=6:

n = 5

p = 5

10000

*/

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

ch2-bitstrings     (Print bits of integers in C/C++)

Contents:     bitstrings.c     BitStrings.cpp 

bitstrings.c          download

#include <stdio.h> // for printf()

#include <limits.h>

#define LENGTH 100 // bits

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of int x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], int x);

// get the bits of unsigned x into bits[], return length of bits[]:

int bitstringu (char bits[], unsigned x);

// get the bits of long x into bits[], return length of bits[]:

int bitstringl (char bits[], long x);

// get the bits of unsigned long x into bits[], return length of bits[]:

int bitstringul (char bits[], unsigned long x);

// get the bits of long long x into bits[], return length of bits[]:

int bitstringll (char bits[], long long x);

// get the bits of unsigned long long x into bits[], return length of bits[]:

int bitstringull (char bits[], unsigned long long x);

int main()

{

  char bits[LENGTH];

  int i; long l; long long ll;

  bitstring(bits, 0);

  printf ("0:\t\t%s\n", bits);

  bitstring(bits, CHAR_MAX);

  printf ("CHAR_MAX:\t%s\n", bits);

  bitstringu(bits, UCHAR_MAX);

  printf ("UCHAR_MAX:\t%s\n", bits);

  bitstring(bits, CHAR_MIN);

  printf ("CHAR_MIN:\t%s\n", bits);

  bitstring(bits, -CHAR_MAX-1);

  printf ("-CHAR_MAX-1:\t%s\n", bits);

  bitstring(bits, SHRT_MAX);

  printf ("SHRT_MAX:\t%s\n", bits);

  bitstringu(bits, USHRT_MAX);

  printf ("USHRT_MAX:\t%s\n", bits);

  bitstring(bits, SHRT_MIN);

  printf ("SHRT_MIN:\t%s\n", bits);

  bitstring(bits, -SHRT_MAX-1);

  printf ("-SHRT_MAX-1:\t%s\n", bits);

  bitstring(bits, INT_MAX);

  printf ("INT_MAX:\t%s\n", bits);

  bitstringu(bits, UINT_MAX);

  printf ("UINT_MAX:\t%s\n", bits);

  bitstring(bits, INT_MIN);

  printf ("INT_MIN:\t%s\n", bits);

  bitstring(bits, -INT_MAX-1);

  printf ("-INT_MAX-1:\t%s\n", bits);

  bitstring(bits, -1);

  printf ("-1:\t\t%s\n", bits);

  i = UINT_MAX; // -1 (modulo 2 arithmetic)

  bitstring(bits, i);

  printf ("%d:\t\t%s\n", i, bits);

  bitstringl(bits, LONG_MAX);

  printf ("LONG_MAX:\t%s\n", bits);

  bitstringul(bits, ULONG_MAX);

  printf ("ULONG_MAX:\t%s\n", bits);

  bitstringl(bits, LONG_MIN);

  printf ("LONG_MIN:\t%s\n", bits);

  bitstringl(bits, -LONG_MAX-1);

  printf ("-LONG_MAX-1:\t%s\n", bits);

  bitstringl(bits, -1l);

  printf ("-1l:\t\t%s\n", bits);

  l = ULONG_MAX; // -1l (modulo 2 arithmetic)

  bitstringl(bits, l);

  printf ("%ldl:\t\t%s\n", l, bits);

  bitstringll(bits, LLONG_MAX);

  printf ("LLONG_MAX:\t%s\n", bits);

  bitstringull(bits, ULLONG_MAX);

  printf ("ULLONG_MAX:\t%s\n", bits);

  bitstringll(bits, LLONG_MIN);

  printf ("LLONG_MIN:\t%s\n", bits);

  bitstringll(bits, -LLONG_MAX-1);

  printf ("-LLONG_MAX-1:\t%s\n", bits);

  bitstringll(bits, -1ll);

  printf ("-1ll:\t\t%s\n", bits);

  ll = ULLONG_MAX; // -1ll (modulo 2 arithmetic)

  bitstringll(bits, ll);

  printf ("%lldll:\t\t%s\n", ll, bits);

  return 0;

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of int x into bits[], return length of bits[] (no of bits):

int bitstring(char bits[], int x)

{

  int i = 0;

  int mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

// get the bits of unsigned x into bits[], return length of bits[]:

int bitstringu(char bits[], unsigned x)

{

  int i = 0;

  unsigned mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

// get the bits of long x into bits[], return length of bits[]:

int bitstringl (char bits[], long x)

{

  int i = 0;

  long mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

// get the bits of unsigned long x into bits[], return length of bits[]:

int bitstringul (char bits[], unsigned long x)

{

  int i = 0;

  unsigned long mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

// get the bits of long long x into bits[], return length of bits[]:

int bitstringll (char bits[], long long x)

{

  int i = 0;

  long long mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

// get the bits of unsigned long long x into bits[], return length of bits[]:

int bitstringull (char bits[], unsigned long long x)

{

  int i = 0;

  unsigned long long mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

/*

gcc bitstrings.c -o bitstrings

./bitstrings

0:              00000000000000000000000000000000

CHAR_MAX:       00000000000000000000000001111111

UCHAR_MAX:      00000000000000000000000011111111

CHAR_MIN:       11111111111111111111111110000000

-CHAR_MAX-1:    11111111111111111111111110000000

SHRT_MAX:       00000000000000000111111111111111

USHRT_MAX:      00000000000000001111111111111111

SHRT_MIN:       11111111111111111000000000000000

-SHRT_MAX-1:    11111111111111111000000000000000

INT_MAX:        01111111111111111111111111111111

UINT_MAX:       11111111111111111111111111111111

INT_MIN:        10000000000000000000000000000000

-INT_MAX-1:     10000000000000000000000000000000

-1:             11111111111111111111111111111111

-1:             11111111111111111111111111111111

LONG_MAX:       0111111111111111111111111111111111111111111111111111111111111111

ULONG_MAX:      1111111111111111111111111111111111111111111111111111111111111111

LONG_MIN:       1000000000000000000000000000000000000000000000000000000000000000

-LONG_MAX-1:    1000000000000000000000000000000000000000000000000000000000000000

-1l:            1111111111111111111111111111111111111111111111111111111111111111

-1l:            1111111111111111111111111111111111111111111111111111111111111111

LLONG_MAX:      0111111111111111111111111111111111111111111111111111111111111111

ULLONG_MAX:     1111111111111111111111111111111111111111111111111111111111111111

LLONG_MIN:      1000000000000000000000000000000000000000000000000000000000000000

-LLONG_MAX-1:   1000000000000000000000000000000000000000000000000000000000000000

-1ll:           1111111111111111111111111111111111111111111111111111111111111111

-1ll:           1111111111111111111111111111111111111111111111111111111111111111

*/

Notes:  The bistring() functions are almost identical. It would be nice if we could have only one function and specify the type of x and mask in main(). This is hard to do in C (see Pseudo-generics_in_C on StackOverflow), but easy in C++ using generics (see BitStrings.cpp below). See also Exercise_3-26 (function print()) on the site Thinking_in_C++_vol_1, Chapter_3 (The C in C++), Section Floats.

Note how -1 and the maximum unsigned of integer types (int, long, long long) have the same bit pattern.

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

BitStrings.cpp          download

#include <cstdio> // for printf()

#include <climits>

#define LENGTH 100 // bits

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

template <typename T>

int bitstring (char bits[], T x);

int main()

{

  char bits[LENGTH];

  int i; long l; long long ll;

  bitstring<int>(bits, 0);

  printf ("0:\t\t%s\n", bits);

  bitstring<int>(bits, CHAR_MAX);

  printf ("CHAR_MAX:\t%s\n", bits);

  bitstring<unsigned>(bits, UCHAR_MAX);

  printf ("UCHAR_MAX:\t%s\n", bits);

  bitstring<int>(bits, CHAR_MIN);

  printf ("CHAR_MIN:\t%s\n", bits);

  bitstring<int>(bits, -CHAR_MAX-1);

  printf ("-CHAR_MAX-1:\t%s\n", bits);

  bitstring<int>(bits, SHRT_MAX);

  printf ("SHRT_MAX:\t%s\n", bits);

  bitstring<unsigned>(bits, USHRT_MAX);

  printf ("USHRT_MAX:\t%s\n", bits);

  bitstring<int>(bits, SHRT_MIN);

  printf ("SHRT_MIN:\t%s\n", bits);

  bitstring<int>(bits, -SHRT_MAX-1);

  printf ("-SHRT_MAX-1:\t%s\n", bits);

  bitstring<int>(bits, INT_MAX);

  printf ("INT_MAX:\t%s\n", bits);

  bitstring<unsigned>(bits, UINT_MAX);

  printf ("UINT_MAX:\t%s\n", bits);

  bitstring<int>(bits, INT_MIN);

  printf ("INT_MIN:\t%s\n", bits);

  bitstring<int>(bits, -INT_MAX-1);

  printf ("-INT_MAX-1:\t%s\n", bits);

  bitstring<int>(bits, -1);

  printf ("-1:\t\t%s\n", bits);

  i = UINT_MAX; // -1 (modulo 2 arithmetic)

  bitstring<int>(bits, i);

  printf ("%d:\t\t%s\n", i, bits);

  bitstring<long>(bits, LONG_MAX);

  printf ("LONG_MAX:\t%s\n", bits);

  bitstring<unsigned long>(bits, ULONG_MAX);

  printf ("ULONG_MAX:\t%s\n", bits);

  bitstring<long>(bits, LONG_MIN);

  printf ("LONG_MIN:\t%s\n", bits);

  bitstring<long>(bits, -LONG_MAX-1);

  printf ("-LONG_MAX-1:\t%s\n", bits);

  bitstring<long>(bits, -1l);

  printf ("-1l:\t\t%s\n", bits);

  l = ULONG_MAX; // -1l (modulo 2 arithmetic)

  bitstring<long>(bits, l);

  printf ("%ldl:\t\t%s\n", l, bits);

  bitstring<long long>(bits, LLONG_MAX);

  printf ("LLONG_MAX:\t%s\n", bits);

  bitstring<unsigned long long>(bits, ULLONG_MAX);

  printf ("ULLONG_MAX:\t%s\n", bits);

  bitstring<long long>(bits, LLONG_MIN);

  printf ("LLONG_MIN:\t%s\n", bits);

  bitstring<long long>(bits, -LLONG_MAX-1);

  printf ("-LLONG_MAX-1:\t%s\n", bits);

  bitstring<long long>(bits, -1ll);

  printf ("-1ll:\t\t%s\n", bits);

  ll = ULLONG_MAX; // -1ll (modulo 2 arithmetic)

  bitstring<long long>(bits, ll);

  printf ("%lldll:\t\t%s\n", ll, bits);

  return 0;

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

template <typename T>

int bitstring(char bits[], T x)

{

  int i = 0;

  T mask = 01; // octal 1

  while (mask != 0) // while(mask)

  {

    if ((x & mask) != 0) // if (x & mask)

    {

      bits[i++] = '1';

    }

    else {bits[i++] = '0';}

    mask <<= 1; // mask = mask << 1;

  }

  bits[i] = '\0';

  reverse(bits, i);

  return i;

}

/*

g++ BitStrings.cpp -o BitStrings

./BitStrings

0:              00000000000000000000000000000000

CHAR_MAX:       00000000000000000000000001111111

UCHAR_MAX:      00000000000000000000000011111111

CHAR_MIN:       11111111111111111111111110000000

-CHAR_MAX-1:    11111111111111111111111110000000

SHRT_MAX:       00000000000000000111111111111111

USHRT_MAX:      00000000000000001111111111111111

SHRT_MIN:       11111111111111111000000000000000

-SHRT_MAX-1:    11111111111111111000000000000000

INT_MAX:        01111111111111111111111111111111

UINT_MAX:       11111111111111111111111111111111

INT_MIN:        10000000000000000000000000000000

-INT_MAX-1:     10000000000000000000000000000000

-1:             11111111111111111111111111111111

-1:             11111111111111111111111111111111

LONG_MAX:       0111111111111111111111111111111111111111111111111111111111111111

ULONG_MAX:      1111111111111111111111111111111111111111111111111111111111111111

LONG_MIN:       1000000000000000000000000000000000000000000000000000000000000000

-LONG_MAX-1:    1000000000000000000000000000000000000000000000000000000000000000

-1l:            1111111111111111111111111111111111111111111111111111111111111111

-1l:            1111111111111111111111111111111111111111111111111111111111111111

LLONG_MAX:      0111111111111111111111111111111111111111111111111111111111111111

ULLONG_MAX:     1111111111111111111111111111111111111111111111111111111111111111

LLONG_MIN:      1000000000000000000000000000000000000000000000000000000000000000

-LLONG_MAX-1:   1000000000000000000000000000000000000000000000000000000000000000

-1ll:           1111111111111111111111111111111111111111111111111111111111111111

-1ll:           1111111111111111111111111111111111111111111111111111111111111111

*/

Note:  See also FloatBinary on the site Thinking_in_C++_vol_1, Chapter_3 (The C in C++), Section Floats. 

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

Exercise 2-6     K&R, p. 49     (setbits)

Exercise 2-6. Write a function setbits(x,p,n,y) that returns x with the last n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

setbits.c          download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// set the last n bits of x starting at position p to the rightmost n bits of y:

unsigned setbits(unsigned x, int p, int n, unsigned y);

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits1[LENGTH], bits2[LENGTH];

  unsigned x, y;

  int len1, len2, min, p, n, diff;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  printf("Give another positive integer: ");

  scanf("%u", &y);

  len1 = bitstring(bits1, x);

  len2 = bitstring(bits2, y);

  printf("x: %s\n", bits1);

  printf("y: %s\n", bits2);

  if (len1 < len2)

  {min = len1;}

  else {min = len2;}

  printf("Set last 0 <= n <= %d bits of x ", min);

  printf("starting at position max(0, n-1) <= p <=%d\n", min-1);

  printf("to the rightmost n bits of y:\n");

  printf ("n = ");

  scanf("%d", &n);

  printf ("p = ");

  scanf("%d", &p);

  x = setbits(x,p,n,y);

  len1 = bitstring(bits1, x);

  diff = n - len1;

  while (diff > 0)

  {

    putchar('0');

    diff--;

  }

  printf("%s\n", bits1);

  return 0;

}

// set the last n bits of x starting at position p to the rightmost n bits of y:

unsigned setbits(unsigned x, int p, int n, unsigned y)

{

  unsigned mask1 = (~0 << n); // ends in n bits of 0s

  mask1 = mask1 << (p+1-n); // 0s are in the proper position in x

  mask1 = mask1 | ~(~0 << (p+1-n)); // last (p+1-n) bits set (to 1)

  mask1 = mask1 | (y << (p+1-n)); // 1..1(rightmost n bits of y)1..1

  unsigned mask2 = ~(~0 << n); // ends in n bits of 1s

  mask2 = mask2 << (p+1-n); // 0..0(n bits of 1)0..0

  x = mask2 | x; // set the required bits of x to 1

  return mask1 & x; // set the required bits of x to the values of y

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc setbits.c -o setbits

./setbits

Give a positive integer: 74

Give another positive integer: 83

x: 1001010

y: 1010011

Set last 0 <= n <= 7 bits of x starting at position max(0, n-1) <= p <=6

to the rightmost n bits of y:

n = 7

p = 6

1010011

./setbits

Give a positive integer: 850

Give another positive integer: 12356

x: 1101010010

y: 11000001000100

Set last 0 <= n <= 10 bits of x starting at position max(0, n-1) <= p <=9

to the rightmost n bits of y:

n = 7

p = 7

1110001000

./setbits

Give a positive integer: 85012356

Give another positive integer: 20125456

x: 101000100010010111110000100

y: 1001100110001011100010000

Set last 0 <= n <= 25 bits of x starting at position max(0, n-1) <= p <=24

to the rightmost n bits of y:

n = 11

p = 24

101110001000010111110000100

*/

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

Exercise 2-7     K&R, p. 49     (Invert bits)

Exercise 2-7. Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e. 1 changed into 0 and vice versa), leaving the others unchanged.

invert.c          download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// invert the last n bits of x starting at position p:

unsigned invert(unsigned x, int p, int n);

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits[LENGTH];

  unsigned x;

  int len, p, n, diff;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  len = bitstring(bits, x);

  printf("x: %s\n", bits);

  printf("Invert last 0 <= n <= %d bits of x ", len);

  printf("starting at position max(0, n-1) <= p <=%d:\n", len-1);

  printf ("n = ");

  scanf("%d", &n);

  printf ("p = ");

  scanf("%d", &p);

  x = invert(x,p,n);

  len = bitstring(bits, x);

  diff = n - len;

  while (diff > 0)

  {

    putchar('0');

    diff--;

  }

  printf("%s\n", bits);

  return 0;

}

// invert the last n bits of x starting at position p:

unsigned invert(unsigned x, int p, int n)

{ // exclusive OR with 1 inverts the bit, exclusive OR with 0 changes nothing

  unsigned mask = ~(~0 << n); // ends in n bits of 1s

  mask = mask << (p+1-n); // 0..0(n bits of 1)0..0

  return mask ^ x; // invert the last n bits of x starting at position p

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc invert.c -o invert

./invert

Give a positive integer: 74

x: 1001010

Invert last 0 <= n <= 7 bits of x starting at position max(0, n-1) <= p <=6:

n = 3

p = 4

1010110

./invert

Give a positive integer: 83

x: 1010011

Invert last 0 <= n <= 7 bits of x starting at position max(0, n-1) <= p <=6:

n = 7

p = 6

0101100

./invert

Give a positive integer: 12345

x: 11000000111001

Invert last 0 <= n <= 14 bits of x starting at position max(0, n-1) <= p <=13:

n = 5

p = 10

11011111111001

*/

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

Exercise 2-8     K&R, p. 49     (rightrot - Right rotation)

Exercise 2-8. Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n bit positions.

rightrot.c          download

#include <stdio.h> // for printf(), scanf(), putchar()

#define LENGTH 100 // bits

// rotate x to the right by n bit positions:

unsigned rightrot(unsigned x, int n);

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits[LENGTH];

  unsigned x;

  int len1, len2, n, diff;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  len1 = bitstring(bits, x);

  printf("x: %s\n", bits);

  printf("Rotate x to the right by 0 <= n <= %d bit positions:\n", len1);

  printf ("n = ");

  scanf("%d", &n);

  x = rightrot(x,n);

  len2 = bitstring(bits, x); // rotated x may be shorter, but not longer

  diff = len1 - len2;

  while (diff > 0)

  {

    putchar('0');

    diff--;

  }

  printf("%s\n", bits);

  return 0;

}

// rotate x to the right by n bit positions:

unsigned rightrot(unsigned x, int n)

{

  char bits[LENGTH];

  int len = bitstring(bits, x); // a sort of bitcount would actually suffice here

  // len >= n, first portion of x has (len-n) length, the second length n

  // save the two portions of x in two masks, then interchange them:

  unsigned mask1 = ~(~0 << (len-n)); // ends in (len-n bits) of 1 (the rest are 0)

  unsigned mask2 = ~(~0 << n); // ends in n bits 0f 1 (the rest are 0)

  mask2 = mask2 & x; // holds second portion (last n bits) of x, the rest is 0

                     // the second portion of x may have leading 0s

  // shifting x to the right may add 1s or 0s at the left end (implementation defined):

  x = x >> n; // first portion of x must have a leading 1 or else it is just 0

  mask1 = x & mask1; // clear first bits of x (if they were 1)

  mask2 = mask2 << (len-n);

  return mask2 | mask1; // interchange the two parts of x

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc rightrot.c -o rightrot

./rightrot

Give a positive integer: 74

x: 1001010

Rotate x to the right by 0 <= n <= 7 bit positions:

n = 0

1001010

./rightrot

Give a positive integer: 74

x: 1001010

Rotate x to the right by 0 <= n <= 7 bit positions:

n = 7

1001010

./rightrot

Give a positive integer: 74

x: 1001010

Rotate x to the right by 0 <= n <= 7 bit positions:

n = 1

0100101 // we keep the initial length of the bit string

./rightrot

Give a positive integer: 74

x: 1001010

Rotate x to the right by 0 <= n <= 7 bit positions:

n = 6 // similar to a left rotate by 1

0010101

*/

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

bitcount.c     K&R, p. 50     (Count set bits in an integer)     download

#include <stdio.h> // for printf(), scanf()

#define LENGTH 100 // bits

int bitcount(unsigned x); // count 1 bits in x

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits[LENGTH];

  unsigned x;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  bitstring(bits,x);

  printf("bitcount(%s): %d\n", bits, bitcount(x));

  return 0;

}

int bitcount(unsigned x) // count set (to 1) bits in x

{

  int b;

  for (b = 0; x != 0; x /= 2)

  { // x >>= 1 and x /= 2 are equivalent, but x /= 2 is safer

    if (x & 01) // 01 is octal 1 (first bits are 0)

    {b++;}

  }

  return b;

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc bitcount.c -o bitcount

./bitcount

Give a positive integer: 74

bitcount(1001010): 3

./bitcount

Give a positive integer: -1

bitcount(11111111111111111111111111111111): 32

./bitcount

Give a positive integer: 4294967295 // UINT_MAX

bitcount(11111111111111111111111111111111): 32

./bitcount

Give a positive integer: -2

bitcount(11111111111111111111111111111110): 31

./bitcount

Give a positive integer: 4294967294

bitcount(11111111111111111111111111111110): 31

./bitcount

Give a positive integer: 0

bitcount(0): 0

./bitcount

Give a positive integer: 32767

bitcount(111111111111111): 15

./bitcount

Give a positive integer: 123

bitcount(1111011): 6

*/

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

*****************************************************************************************

Exercise 2-9     K&R, p. 51     (Fast bitcount)

Exercise 2-9. In a two's complement number system, x &= (x-1) deletes the rightmost bit in x. Explain why, Use this observation to write a faster version of bitcount().

fastbitcount.c          download

#include <stdio.h> // for printf(), scanf()

#define LENGTH 100 // bits

int fastbitcount(unsigned x); // count 1 bits in x

// reverse s[], knowing its length:

void reverse(char s[], int len);

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x);

int main()

{

  char bits[LENGTH];

  unsigned x;

  printf("Give a positive integer: ");

  scanf("%u", &x);

  bitstring(bits,x);

  printf("fastbitcount(%s): %d\n", bits, fastbitcount(x));

  return 0;

}

int fastbitcount(unsigned x) // count set (to 1) bits in x

{

  int b;

  for (b = 0; x != 0; x &= (x-1))

  { // x != 0 means x has at least one bit of 1 (or else x == 0)

    // if x is odd, the last bit of x is 1, so x-1 is x with last bit 0,

    // then x = x & (x-1) is x with the last 1 bit removed (set to 0)

    // if x is even, last bit of x is 0, but x != 0 means x has at least one bit of 1,

    // then x-1 sets the last 1 bit of x to 0, while setting the last 0 bits of x to 1:

    // 2 == 10, 2-1 == 1 == 01; 4 == 100, 4-1 == 3 == 011;

    // 6 == 110, 6-1 == 5 == 101; 12 == 1100, 12-1 == 11 == 1011;

    // in all these cases, x & (x-1) is x with the last 1 bit removed (set to 0)

    b++; // at each iteration we remove exactly one bit of 1 from x

  }

  return b;

}

// reverse s[], knowing its length:

void reverse(char s[], int len)

{

  int i = 0, j = len-1;

  char temp;

  while (i < j)

  {

    temp = s[i];

    s[i] = s[j];

    s[j] = temp;

    i++;

    j--;

  }

}

// get the bits of x into bits[], return length of bits[] (no of bits):

int bitstring (char bits[], unsigned x)

{

  int i = 0;

  if (x == 0)

  {

    bits[i++] = '0';

    bits[i] = '\0';

    return i;

  }

  while (x > 0)

  { // last bit gives the parity:

    bits[i++] = '0' + x % 2; // 0 for even, 1 for odd

    x /= 2; // x = x / 2; // lose last bit

  }

  bits[i] = '\0'; // end the string

  reverse(bits, i);

  return i;

}

/*

gcc fastbitcount.c -o fastbitcount

./fastbitcount

Give a positive integer: 74

fastbitcount(1001010): 3

./fastbitcount

Give a positive integer: -1

fastbitcount(11111111111111111111111111111111): 32

./fastbitcount

Give a positive integer: 4294967295 // UINT_MAX

fastbitcount(11111111111111111111111111111111): 32

./fastbitcount

Give a positive integer: -2

fastbitcount(11111111111111111111111111111110): 31

./fastbitcount

Give a positive integer: 4294967294

fastbitcount(11111111111111111111111111111110): 31

./fastbitcount

Give a positive integer: 0

fastbitcount(0): 0

./fastbitcount

Give a positive integer: 32767

fastbitcount(111111111111111): 15

./fastbitcount

Give a positive integer: 123

fastbitcount(1111011): 6

*/

Note: fastbitcount() is faster than bitcount() because it has fewer iterations (see bitcount.c).

 No. of iterations of bitcount(x): no of bits of x, including inner 0 bits, which is returned by bitstring(bits,x).

No. of iterations of fastbitcount(): no of 1 (set) bits of x.

Chapter_2     ch2-Strings                              Back_to_Top                                 ch2-Conditionals