[Algorithm] Math - Is a power of two - 하고싶은거하는

2의 거듭제곱이란?

2의 거듭제곱이란 $2^n$으로 표현될 수 있는 숫자를 말하며, 여기서 $n$은 0 이상의 정수입니다. 예를 들어:

$2^0 = 1$
$2^1 = 2$
$2^2 = 4$
$2^3 = 8$
$2^4 = 16$, 등등.

이진수로 표현했을 때, 2의 거듭제곱은 오직 하나의 비트만이 1로 설정되어 있습니다. 예를 들어:

1의 이진수는 0001
2의 이진수는 0010
4의 이진수는 0100
8의 이진수는 1000입니다.

2의 거듭제곱 검사 사용 사례

메모리 할당: 컴퓨팅에서는 메모리 할당 크기(예: 2KB, 4KB, 8KB)가 보통 2의 거듭제곱으로 이루어집니다.
해싱(Hashing): 해시 테이블의 크기는 보통 2의 거듭제곱으로 설정되어 나눗셈 연산을 단순화합니다.
비트 조작: 비트 조작을 통한 최적화에서 2의 거듭제곱은 중요한 역할을 합니다.
자료구조: 이진 힙(binary heap)과 같은 힙 기반 자료구조에서 2의 거듭제곱 크기는 연산을 단순하게 만듭니다.
그래픽 및 비디오: 컴퓨터 그래픽에서 텍스처 크기를 2의 거듭제곱으로 설정하는 것이 요구되는 경우가 많습니다.

2의 거듭제곱을 확인하는 방법?

2의 거듭제곱인지 확인하는 방법에는 여러 가지가 있지만, 비트 연산을 사용한 방법이 가장 효율적입니다.

비트 연산을 통한 확인 설명:

숫자 $n$이 2의 거듭제곱이라면, $n$은 이진수로 변환했을 때 하나의 비트만 1로 설정됩니다. 따라서 n & (n - 1) 연산 결과가 0이면 $n$은 2의 거듭제곱입니다. 왜냐하면 $n$에서 1을 빼면 가장 낮은 1 비트 이후의 모든 비트가 반전되기 때문입니다.

예시:

$n = 8$ ($1000_2$), $n - 1 = 7$ ($0111_2$), 그리고 $n & (n - 1) = 0$
$n = 6$ ($0110_2$), $n - 1 = 5$ ($0101_2$), 그리고 $n & (n - 1) \neq 0$

JavaScript에서 2의 거듭제곱 확인 예제

function isPowerOfTwo(n) {
  // 2의 거듭제곱은 0보다 크고, 하나의 비트만 설정되어 있어야 함.
  return n > 0 && (n & (n - 1)) === 0;
}

console.log(isPowerOfTwo(1)); // true (2^0)
console.log(isPowerOfTwo(2)); // true (2^1)
console.log(isPowerOfTwo(3)); // false
console.log(isPowerOfTwo(4)); // true (2^2)
console.log(isPowerOfTwo(5)); // false

Rust에서 2의 거듭제곱 확인 예제

fn is_power_of_two(n: u32) -> bool {
    n > 0 && (n & (n - 1)) == 0
}

fn main() {
    println!("{}", is_power_of_two(1));  // true (2^0)
    println!("{}", is_power_of_two(2));  // true (2^1)
    println!("{}", is_power_of_two(3));  // false
    println!("{}", is_power_of_two(4));  // true (2^2)
    println!("{}", is_power_of_two(5));  // false
}

요약:

2의 거듭제곱은 $2^n$으로 표현될 수 있는 숫자입니다. 2의 거듭제곱인지 확인하는 것은 메모리 관리, 해싱, 비트 조작 등에서 자주 사용됩니다. 이를 확인하는 가장 효율적인 방법은 비트 연산을 사용하는 것이며, n & (n - 1) == 0으로 간단하게 구현할 수 있습니다. JavaScript와 Rust 모두 이 검사를 쉽게 구현할 수 있습니다.

What is “Power of Two”?

A number is called a power of two if it can be written as $2^n$ where $n$ is a non-negative integer. For example:

$2^0 = 1$
$2^1 = 2$
$2^2 = 4$
$2^3 = 8$
$2^4 = 16$, and so on.

In binary form, a power of two has only one bit set to 1. For example:

1 in binary is 0001
2 in binary is 0010
4 in binary is 0100
8 in binary is 1000

Use Cases of Checking Power of Two

Memory Allocation: Powers of two are often used in computing for allocating memory (e.g., 2KB, 4KB, 8KB).
Hashing: Hash table sizes are often set as powers of two to simplify modulo operations.
Bit Manipulation: Powers of two play a significant role in bitwise operations for optimizations.
Data Structures: In certain algorithms like heap-based data structures (like binary heaps), power of two sizes can simplify operations.
Graphics and Video: Power of two sizes are often required for textures in computer graphics.

How to Check if a Number is a Power of Two?

There are multiple ways to check if a number is a power of two. The most efficient method involves bitwise manipulation.

Explanation of Bitwise Check:

For a number $n$, if $n$ is a power of two, then $n$ has exactly one bit set to 1 in its binary form. So, the expression n & (n - 1) will be zero if $n$ is a power of two, because subtracting 1 from $n$ flips all bits after the least significant 1 bit.

For example:

$n = 8$ ($1000_2$), $n - 1 = 7$ ($0111_2$), and $n & (n - 1) = 0$
$n = 6$ ($0110_2$), $n - 1 = 5$ ($0101_2$), and $n & (n - 1) \neq 0$

JavaScript Example for Checking Power of Two

function isPowerOfTwo(n) {
  // Power of two is greater than 0 and has only one bit set.
  return n > 0 && (n & (n - 1)) === 0;
}

console.log(isPowerOfTwo(1)); // true (2^0)
console.log(isPowerOfTwo(2)); // true (2^1)
console.log(isPowerOfTwo(3)); // false
console.log(isPowerOfTwo(4)); // true (2^2)
console.log(isPowerOfTwo(5)); // false

Rust Example for Checking Power of Two

fn is_power_of_two(n: u32) -> bool {
    n > 0 && (n & (n - 1)) == 0
}

fn main() {
    println!("{}", is_power_of_two(1));  // true (2^0)
    println!("{}", is_power_of_two(2));  // true (2^1)
    println!("{}", is_power_of_two(3));  // false
    println!("{}", is_power_of_two(4));  // true (2^2)
    println!("{}", is_power_of_two(5));  // false
}

Summary:

A power of two is any number that can be written as $2^n$ for some non-negative integer $n$. Checking if a number is a power of two is commonly used in memory management, hashing, and bit manipulation. The most efficient way to check this involves using bitwise operations. Both JavaScript and Rust offer simple implementations to verify if a number is a power of two using the expression n & (n - 1) == 0.

[Algorithm] Math - Is a power of two

수학 2의 거듭제곱 판별법