# CommonTwos

A utility library for finding common factors of 2 between two numbers using efficient bitwise operations.

## Overview

CommonTwos provides algorithms for finding the greatest common divisor (GCD) by counting trailing zeros in binary representation. This is particularly useful for mathematical optimizations and number theory applications.

## Features

- **Efficient bitwise operations** for finding common factors
- **Type-safe** with comprehensive specs
- **Well-documented** with examples and use cases
- **Production-ready** with full development tooling

## Installation

The package can be installed by adding `common_twos` to your list of dependencies in `mix.exs`:

```elixir
def deps do
  [
    {:common_twos, "~> 1.0"}
  ]
end
```

## Usage

### Basic Usage

```elixir
# Find common factors of 2 between two numbers
{shift, reduced_a, reduced_b} = CommonTwos.of(12, 8)
# Returns: {2, 3, 2}

# The shift count represents common factors of 2
# The reduced values are the numbers after removing those factors
```

### Examples

```elixir
# Numbers with common factors of 2
CommonTwos.of(16, 24)  # Returns: {3, 2, 3}
CommonTwos.of(8, 32)   # Returns: {3, 1, 4}

# Numbers without common factors of 2
CommonTwos.of(7, 11)   # Returns: {0, 7, 11}
CommonTwos.of(3, 5)    # Returns: {0, 3, 5}

# Edge cases
CommonTwos.of(0, 8)    # Returns: {3, 0, 1}
CommonTwos.of(0, 0)    # Returns: {0, 0, 0}
```

## Algorithm

The algorithm works by:

1. **Counting trailing zeros**: Both numbers are shifted right until at least one has a 1 in the least significant bit
2. **Tracking shifts**: The number of shifts performed is the count of common factors of 2
3. **Returning results**: A tuple containing the shift count and the reduced values

This is particularly efficient because:
- Uses bitwise operations (`bor`, `band`, `bsr`)
- Avoids division operations
- Works well with binary number representations

## API Reference

### `CommonTwos.of/2`

```elixir
@spec of(non_neg_integer(), non_neg_integer()) ::
        {non_neg_integer(), non_neg_integer(), non_neg_integer()}
```

Finds the common factors of 2 between two numbers.

**Parameters:**
- `a` - First non-negative integer
- `b` - Second non-negative integer

**Returns:**
A tuple `{shift, reduced_a, reduced_b}` where:
- `shift` - The number of common factors of 2 (trailing zeros in binary)
- `reduced_a` - The value of `a` after removing common factors of 2
- `reduced_b` - The value of `b` after removing common factors of 2

## 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](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.