common_twos

defmodule CommonTwos do
  @moduledoc """
  A utility module for finding the greatest common divisor (GCD) of two numbers
  by counting trailing zeros in their binary representation.

  This module provides efficient algorithms for finding common factors between
  two integers using bitwise operations. The primary function `of/2` returns
  a tuple containing the shift count and the reduced values after removing
  common factors of 2.

  ## Examples

      iex> CommonTwos.of(12, 8)
      {2, 3, 2}

      iex> CommonTwos.of(16, 24)
      {3, 2, 3}

      iex> CommonTwos.of(7, 11)
      {0, 7, 11}

  ## Algorithm

  The algorithm works by:
  1. Counting how many trailing zeros both numbers have in common
  2. Shifting both numbers right by that amount
  3. Returning the shift count and the reduced numbers

  This is particularly useful for:
  - Finding common factors efficiently
  - Optimizing mathematical operations
  - Number theory applications
  """

  @doc """
  Finds the common factors of 2 between two numbers and returns the shift count
  along with the reduced values.

  ## 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

  ## Examples

      iex> CommonTwos.of(12, 8)
      {2, 3, 2}

      iex> CommonTwos.of(16, 24)
      {3, 2, 3}

      iex> CommonTwos.of(7, 11)
      {0, 7, 11}

      iex> CommonTwos.of(0, 8)
      {3, 0, 1}

  ## Notes

  - If both numbers are 0, the result will be `{0, 0, 0}`
  - If one number is 0, the shift count will be based on the non-zero number
  - The algorithm uses bitwise operations for efficiency
  """
  @spec of(non_neg_integer(), non_neg_integer()) ::
          {non_neg_integer(), non_neg_integer(), non_neg_integer()}
  def of(a, b), do: sub({0, a, b})

  # Private function that performs the recursive bitwise operations
  # to find common factors of 2 between the two numbers
  defp sub({shift, a, b}) when Bitwise.bor(a, b) |> Bitwise.band(1) != 0 do
    {shift, a, b}
  end

  defp sub({shift, a, b}), do: sub({shift + 1, Bitwise.bsr(a, 1), Bitwise.bsr(b, 1)})
end