Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Bit-Level Programming in C: A Hands-On Tutorial for CSCI 247 Project 1

Master bit manipulation, two's complement arithmetic, and floating-point operations with this step-by-step tutorial inspired by CSCI 247 Project 1. Perfect for students learning low-level C programming.

bit manipulation in C CSCI 247 project 1 bitwise operators tutorial two's complement arithmetic floating point bit representation C programming assignments bit counting algorithm logical shift right C negate without negation fitsBits function float_neg implementation float_twice C code low level programming C systems programming tutorial popcount in C bit level operations examples

Introduction to Bit Manipulation in C

Bit manipulation is a fundamental skill in systems programming, used in everything from network protocols to graphics rendering. In this tutorial, we'll explore the core concepts behind CSCI 247 Project 1: manipulating bits. You'll learn how to implement bitwise operations, two's complement arithmetic, and floating-point bit-level functions using only a limited set of operators. This mirrors real-world challenges in embedded systems, game development, and AI hardware acceleration.

For example, when you play a game like Fortnite, hit detection and network packets rely on efficient bit-level operations to minimize latency. Similarly, machine learning models quantize weights using bit manipulation to run on mobile devices.

Bitwise Operators and the bitAnd Puzzle

The first puzzle is bitAnd(x,y), which computes x & y using only | and ~. This tests your understanding of De Morgan's laws. Recall that x & y = ~(~x | ~y). Here's a simple implementation:

int bitAnd(int x, int y) {
  return ~(~x | ~y);
}

This uses exactly 3 operators, well within the limit of 8. This pattern is essential for building higher-level operations like masking and bit clearing.

Extracting Bytes with getByte

The getByte(x,n) function extracts byte n from x. For example, getByte(0x12345678, 1) returns 0x56. The trick is to shift right by n*8 bits and mask with 0xFF:

int getByte(int x, int n) {
  return (x >> (n << 3)) & 0xFF;
}

Note: we use n << 3 instead of n*8 because shifts are faster. This function is used in network byte order conversion and file format parsing.

Logical Shift Right

In C, the right shift operator >> on signed integers is arithmetic (sign-extending). To perform a logical shift (fill with zeros), implement logicalShift(x,n). The trick: create a mask that zeros out the sign bits:

int logicalShift(int x, int n) {
  int mask = ~(((1 << 31) >> n) << 1);
  return (x >> n) & mask;
}

This mask clears the top n bits after an arithmetic shift. Logical shifts are critical for unsigned operations and bit field extraction.

Counting Bits with bitCount

Counting the number of 1's in an integer is a classic problem. The bitCount(x) puzzle uses a divide-and-conquer approach (popcount). For example, using a 5-bit mask pattern:

int bitCount(int x) {
  int mask = 0x55555555;
  x = (x & mask) + ((x >> 1) & mask);
  mask = 0x33333333;
  x = (x & mask) + ((x >> 2) & mask);
  mask = 0x0F0F0F0F;
  x = (x & mask) + ((x >> 4) & mask);
  mask = 0x00FF00FF;
  x = (x & mask) + ((x >> 8) & mask);
  mask = 0x0000FFFF;
  x = (x & mask) + ((x >> 16) & mask);
  return x;
}

This uses only bitwise and addition, no loops. Bit counting is used in cryptography, error detection, and machine learning (e.g., binary neural networks).

Two's Complement Arithmetic Functions

tmin() - Most Negative Integer

The most negative two's complement integer is 0x80000000. Implement tmin() as:

int tmin(void) {
  return 1 << 31;
}

This is a one-liner that demonstrates the asymmetry of two's complement.

fitsBits(x,n)

Determine if x can be represented in n bits (two's complement). The trick: shift left and right to see if sign extension matches:

int fitsBits(int x, int n) {
  int shift = 32 + ~n + 1; // 32 - n
  int y = (x << shift) >> shift;
  return !(x ^ y);
}

This is useful for optimizing data types in memory-constrained systems.

divpwr2(x,n)

Compute x/2^n with rounding toward zero. For negative numbers, you need to add a bias:

int divpwr2(int x, int n) {
  int bias = (x >> 31) & ((1 << n) + ~0);
  return (x + bias) >> n;
}

This mimics hardware division used in DSP and graphics.

negate(x)

Return -x without using negation. The formula: ~x + 1:

int negate(int x) {
  return ~x + 1;
}

This is the essence of two's complement negation.

isPositive(x)

Return 1 if x > 0, else 0. Watch out for zero and negative numbers:

int isPositive(int x) {
  return !((x >> 31) | (!x));
}

This uses sign bit and zero check. Positive numbers are crucial in conditional logic.

ilog2(x)

Compute floor(log2(x)). This is essentially finding the highest set bit. Use binary search with shifts:

int ilog2(int x) {
  int y = 0;
  y = (!!(x >> 16)) << 4;
  y = y + ((!!(x >> (y + 8))) << 3);
  y = y + ((!!(x >> (y + 4))) << 2);
  y = y + ((!!(x >> (y + 2))) << 1);
  y = y + (!!(x >> (y + 1)));
  return y;
}

This algorithm is used in priority encoders and hash tables.

Floating-Point Bit-Level Operations

IEEE 754 single-precision floats have sign (1 bit), exponent (8 bits), and fraction (23 bits). You'll implement float_neg and float_twice using only integer operations.

float_neg(uf)

Return the bit representation of -f. Simply flip the sign bit, but handle NaN:

unsigned float_neg(unsigned uf) {
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned frac = uf & 0x7FFFFF;
  if (exp == 0xFF && frac != 0) return uf; // NaN
  return uf ^ 0x80000000;
}

This is used in graphics and physics engines to negate vectors.

float_twice(uf)

Compute 2*f. For normalized numbers, increment the exponent; for denormalized, shift fraction left. Handle infinity and NaN:

unsigned float_twice(unsigned uf) {
  unsigned sign = uf & 0x80000000;
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned frac = uf & 0x7FFFFF;
  if (exp == 0xFF) return uf; // NaN or inf
  if (exp == 0) {
    frac <<= 1;
    if (frac & 0x800000) { // overflow to normalized
      exp = 1;
      frac &= 0x7FFFFF;
    }
    return sign | (exp << 23) | frac;
  }
  exp++;
  if (exp == 0xFF) { // overflow to inf
    return sign | 0x7F800000;
  }
  return sign | (exp << 23) | frac;
}

This demonstrates the mechanics of floating-point arithmetic, essential for scientific computing and AI model inference.

Testing and Debugging with btest

Use the provided btest tool to verify your functions. Compile with make and test individual functions:

./btest -f bitAnd -1 5 -2 3

This tests bitAnd(5,3). The dlc tool checks operator count and coding rules. Always run dlc before submitting to avoid point deductions.

Real-World Applications and Trends

Bit manipulation is everywhere. In the latest Apple M4 chip, bit-level operations accelerate matrix multiplications for AI. In autonomous vehicles, sensor fusion uses bitwise operations for efficient data packing. Even in TikTok's recommendation algorithm, bit counting helps hash user interactions. Understanding these basics will give you an edge in systems programming, embedded development, and high-performance computing.

Conclusion

Mastering bit manipulation in C is a rite of passage for computer scientists. By solving these puzzles, you'll think more deeply about how data is represented and processed. Practice with the provided tools, and remember: every great hacker started with bits and bytes. Happy coding!