Trailing Zeros

A fast and efficient Elixir library for counting trailing zeros in the binary representation of integers.

Features

• High Performance: O(log n) time complexity using optimized bitwise operations
• Memory Efficient: O(1) space complexity with tail-recursive implementation
• Comprehensive Testing: 14 test cases covering edge cases and typical scenarios
• Well Documented: Complete documentation with examples and use cases
• Type Safe: Full type specifications for better development experience

Installation

Add trailing_zeros to your list of dependencies in mix.exs:

def deps do
  [
    {:trailing_zeros, "~> 1.0"}
  ]
end

Then install dependencies:

mix deps.get

Usage

# Count trailing zeros in binary representation
TrailingZeros.of(0)    # Returns: 0
TrailingZeros.of(8)    # Returns: 3 (8 = 1000 in binary)
TrailingZeros.of(12)   # Returns: 2 (12 = 1100 in binary)
TrailingZeros.of(16)   # Returns: 4 (16 = 10000 in binary)

Algorithm

The library uses an efficient bit manipulation approach:

1. Base case: Return 0 for input 0
2. Recursive counting: Use bitwise operations to check the least significant bit
3. Bit shifting: Right-shift the number to examine the next bit
4. Accumulation: Count consecutive zeros until a 1 is encountered

Performance Characteristics

• Time Complexity: O(log n) - proportional to the number of bits
• Space Complexity: O(1) - constant space usage (tail-recursive)
• Bitwise Operations: Uses efficient Bitwise.band/2 and Bitwise.bsr/2

Mathematical Properties

• For any number n, if TrailingZeros.of(n) = k, then n is divisible by 2^k
• Powers of 2 have trailing zero counts equal to their exponent
• Odd numbers always have 0 trailing zeros
• The maximum trailing zeros for a 32-bit integer is 31 (for 0)

License

Copyright (c) 2025 University of Kitakyushu

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Changelog

See CHANGELOG.md for a list of changes and version history.

Acknowledgments

• Built with modern Elixir development practices
• Uses efficient bitwise operations for optimal performance
• Comprehensive test coverage ensures reliability
• Well-documented for easy integration and learning