#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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#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
*/
Note how -1 and the maximum unsigned of integer types (int, long, long long) have the same bit pattern.
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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.
#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. 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.
#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. Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n bit positions.
#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
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#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. 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().
#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
*/
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.