Skip to content

CMSC 14300: Practice Set 3 - Bitwise Operations & Arrays

Practice for the material in Week 2: operators, binary/hex, bit manipulation, and arrays. This is good preparation for the next quiz.

Work in a fresh directory and compile everything with warnings on:

mkdir -p ~/cmsc14300/lec03-pset && cd ~/cmsc14300/lec03-pset
clang -Wall -Wextra -std=c17 problem1.c -o problem1

If your compiler prints a warning, treat it as something to fix - warnings are the compiler trying to help you. When a value is "a bag of bits," reach for unsigned int and read it with %u.

Problem 1 - Count and find the bits

Read an unsigned int and report three things about its bits:

  1. its population count - how many bits are set to 1;
  2. the position of its lowest set bit (bit 0 is the least significant), or -1 if the value is 0;
  3. whether it is a power of two (1 if yes, 0 if no).

Use the shift-then-mask idiom (v >> i) & 1 to inspect bit i.

Enter a number: 40
set bits: 2
lowest set bit: 3
power of two: 0

Enter a number: 64
set bits: 1
lowest set bit: 6
power of two: 1

  • A value is a power of two exactly when it has a single set bit. You can use your popcount answer, or the one-line trick v != 0 && (v & (v - 1)) == 0 - work out on paper why v & (v - 1) clears the lowest set bit.

Problem 2 - A flags toolkit

A single unsigned int can pack 32 on/off settings. Write the four standard bit operations as functions, then drive them from main:

unsigned int set_bit(unsigned int x, int n);     /* turn bit n on        */
unsigned int clear_bit(unsigned int x, int n);   /* turn bit n off       */
unsigned int toggle_bit(unsigned int x, int n);  /* flip bit n           */
int          is_set(unsigned int x, int n);      /* 1 if bit n is on     */

In main, start from flags = 0, then: set bits 1 and 3, clear bit 1, toggle bit 0, and after each step print the flags in binary (reuse a print_binary helper). Finish by listing which of bits 0 through 7 are currently on.

after set 1,3:  00001010
after clear 1:  00001000
after toggle 0: 00001001
bits on (0-7): 0 3
  • Recall the four idioms: |= (1u << n) set, &= ~(1u << n) clear, ^= (1u << n) toggle, (x >> n) & 1 test.

Problem 3 - Array statistics

Read a count n, then n integers into an array (you may assume n <= 100). Print their sum, minimum, maximum, average (as a double), and how many values are above the average.

How many numbers? 5
Enter 5 numbers: 64 8 23 91 19
sum: 205
min: 8
max: 91
average: 41.00
above average: 2
  • Seed min and max from element 0, not from 0 - otherwise an all-negative array reports a wrong maximum.
  • Mind the integer-division trap for the average: cast to double before dividing.
  • "Above average" needs two passes: you cannot count it until the average is known, so compute the average first, then walk the array again comparing each element against it.
  • Stay inside indices 0 .. n-1; there is no bounds checking.

Problem 4 - Functions over arrays

Package a few array routines as functions (prototypes at the top, definitions below main):

void rotate_left(int a[], int n);  /* shift every element one slot left, wrapping the first to the end */
int  index_of_max(int a[], int n); /* index of the largest element      */
int  count_even(int a[], int n);   /* how many elements are even        */

Read n and n integers, then print the index of the max, the number of even values, and the array after rotating it one slot to the left.

How many numbers? 4
Enter 4 numbers: 10 25 30 7
index of max: 2
even count: 2
rotated left: 25 30 7 10
  • For rotate_left, save a[0] in a temporary, shift a[1..n-1] down one slot, then drop the saved value into a[n-1]. Do it in place - no second array needed.
  • Remember these functions cannot see the array's size on their own, which is why each one takes n.

Problem 5 - A bitset (arrays meet bits)

This problem combines both halves of the week. You will track which numbers in the range 0..255 appear in the input using a bitset: an array of unsigned int used as one long wall of bits. With 32 bits per unsigned int, you need 256 / 32 = 8 of them.

unsigned int seen[8] = {0};   /* 8 * 32 = 256 bits, all clear */

For a value v in 0..255:

  • it lives in word v / 32 at bit position v % 32;
  • mark it with seen[v / 32] |= (1u << (v % 32));
  • test it with (seen[v / 32] >> (v % 32)) & 1.

Read integers until end of input (or until a sentinel -1), ignoring any outside 0..255. Then print every value 0..255 that appeared, in increasing order, and how many distinct values were seen.

Enter numbers (-1 to stop): 5 200 5 5 42 200 -1
present: 5 42 200
distinct: 3
  • Notice you never store the numbers themselves - just one bit each. Tracking 256 possibilities costs 32 bytes total.
  • Check your understanding: why does feeding 5 three times still report it once? Which line makes that happen?

Self-check

You're ready for the upcoming quiz material if you can, without looking it up:

  • Convert a small number between decimal, binary, and hex by hand, and explain why one hex digit maps to exactly four bits.
  • State what &, |, ^, ~, <<, and >> each do, and how bitwise & differs from logical &&.
  • Write the four mask idioms - set, clear, toggle, test - from memory, and say why each one works.
  • Explain why a C array does not know its own length, why a function that takes an array also needs its size, and what "no bounds checking" means for your code.