mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
Basupre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>Christian Clausscclauss* bit_manipulation: add parity, next_power_of_two, rotate_bits (Author: Basuki Nath) and extend doctests * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * updating DIRECTORY.md --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com> Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
71 lines
1.8 KiB
Python
71 lines
1.8 KiB
Python
"""
|
|
Author : Basuki Nath
|
|
Date : 2025-10-04
|
|
|
|
Bit rotation helpers for 32-bit unsigned integers.
|
|
"""
|
|
|
|
|
|
def rotate_left32(x: int, k: int) -> int:
|
|
"""
|
|
Rotate the lower 32 bits of x left by k and return result in 0..2**32-1.
|
|
|
|
>>> rotate_left32(1, 1)
|
|
2
|
|
>>> rotate_left32(1, 31)
|
|
2147483648
|
|
>>> rotate_left32(0x80000000, 1)
|
|
1
|
|
>>> rotate_left32(0x12345678, 4)
|
|
591751041
|
|
>>> rotate_left32(-1, 3)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: x must be a non-negative integer
|
|
>>> rotate_left32(1, -1)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: k must be non-negative
|
|
"""
|
|
if not isinstance(x, int) or x < 0:
|
|
raise ValueError("x must be a non-negative integer")
|
|
if not isinstance(k, int) or k < 0:
|
|
raise ValueError("k must be non-negative")
|
|
mask = (1 << 32) - 1
|
|
k &= 31
|
|
return ((x << k) & mask) | ((x & mask) >> (32 - k))
|
|
|
|
|
|
def rotate_right32(x: int, k: int) -> int:
|
|
"""
|
|
Rotate the lower 32 bits of x right by k and return result in 0..2**32-1.
|
|
|
|
>>> rotate_right32(2, 1)
|
|
1
|
|
>>> rotate_right32(1, 1)
|
|
2147483648
|
|
>>> rotate_right32(0x12345678, 4)
|
|
2166572391
|
|
>>> rotate_right32(-1, 1)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: x must be a non-negative integer
|
|
>>> rotate_right32(1, -3)
|
|
Traceback (most recent call last):
|
|
...
|
|
ValueError: k must be non-negative
|
|
"""
|
|
if not isinstance(x, int) or x < 0:
|
|
raise ValueError("x must be a non-negative integer")
|
|
if not isinstance(k, int) or k < 0:
|
|
raise ValueError("k must be non-negative")
|
|
mask = (1 << 32) - 1
|
|
k &= 31
|
|
return ((x & mask) >> k) | ((x << (32 - k)) & mask)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod()
|