Skip to content

is_power_of_2

Mallikarjunarao Kosuri edited this page Jul 14, 2024 · 1 revision

The is_power_of_2 function checks if a given 8-bit unsigned integer is a power of 2. A number is a power of 2 if it has exactly one bit set in its binary representation.

Function Code

uint8_t is_power_of_2(uint8_t x)
{
    return x && !(x & (x - 1));
}

How It Works

  1. Condition 1: x && ...

    • This checks if x is not zero. If x is zero, it cannot be a power of 2, and the function returns 0 (false).
  2. Condition 2: !(x & (x - 1))

    • This checks if x is a power of 2 using the bitwise AND operation:
      • (x - 1) flips all the bits after the rightmost set bit of x (including the rightmost set bit).
      • x & (x - 1) is 0 if and only if x has exactly one bit set (i.e., x is a power of 2).

Example

Let's consider an example where x = 8.

  1. Binary Representation of 8:

    • 8 in binary is 00001000.
  2. Step-by-Step Execution:

  • Initial Values:
    • x = 8 (binary 00001000)
return x && !(x & (x - 1));
  • Detailed Execution:
  1. Condition 1:

    • x is 8, which is not zero, so x && ... is true.
  2. Condition 2:

    • Calculate x - 1:
      • x = 8 (binary 00001000)
      • x - 1 = 7 (binary 00000111)
    • Perform x & (x - 1):
      • x = 8 (binary 00001000)
      • x - 1 = 7 (binary 00000111)
      • x & (x - 1) = 00001000 & 00000111 = 00000000
    • !(x & (x - 1)) is !0, which is 1 (true).
  • Result:
    • The function returns 1, indicating that 8 is a power of 2.

Textual Diagram

x = 8 (binary 00001000)

Step 1: Check if x is non-zero
x       : 00001000
Condition: x && ... => true

Step 2: Check if x & (x - 1) is zero
x       : 00001000
x - 1   : 00000111
x & (x - 1) : 00000000
Condition: !(x & (x - 1)) => !0 => 1 (true)

Result: 8 is a power of 2

Use Cases

When to Use

  • Checking Power of 2: Determine if a number is a power of 2, which is useful in algorithms that operate on power-of-2 sizes, such as certain FFT (Fast Fourier Transform) implementations or memory allocation strategies.

Use Cases in Embedded Systems

  • Memory Management: Memory sizes in embedded systems are often powers of 2 (e.g., 256 bytes, 512 bytes, 1 KB). This function helps validate memory sizes.
  • Timing and Frequency Dividers: Dividers for timing and frequency in embedded systems often use powers of 2. This function can help in configuring timers.
  • Optimization: Algorithms that require or benefit from power-of-2 sizes can use this function to ensure correct input.

Example in Embedded Systems

Let's consider using this function to verify memory allocation in an embedded system:

#include <stdint.h>
#include "bitops.h"

void allocate_memory(uint8_t size)
{
    if (is_power_of_2(size)) {
        printf("Allocating %d bytes of memory.\n", size);
        // Memory allocation logic here
    } else {
        printf("Error: Size %d is not a power of 2.\n", size);
    }
}

int main()
{
    uint8_t size = 16;
    allocate_memory(size); // Valid size

    size = 20;
    allocate_memory(size); // Invalid size

    return 0;
}
Clone this wiki locally