//******************************************************************************************************//  BitMath.cs - Gbtc////  Copyright © 2014, Grid Protection Alliance.  All Rights Reserved.////  Licensed to the Grid Protection Alliance (GPA) under one or more contributor license agreements. See//  the NOTICE file distributed with this work for additional information regarding copyright ownership.//  The GPA licenses this file to you under the MIT License (MIT), 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.opensource.org/licenses/MIT////  Unless agreed to in writing, the subject software distributed under the License is distributed on an//  "AS-IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. Refer to the//  License for the specific language governing permissions and limitations.////  Code Modification History://  ----------------------------------------------------------------------------------------------------//  06/08/2012 - Steven E. Chisholm//       Generated original version of source code. //       ////****************************************************************************************************** using System;using System.Collections.Generic; namespace GSF{    /// <summary>    /// Contains some random and useful functions.    /// </summary>    public static class BitMath    {        #region [ Is Power Of Two ]         /// <summary>        /// Determines if the number is a power of 2.        /// </summary>        /// <param name="value">The value to check power of two properties</param>        /// <returns></returns>        /// <exception cref="ArgumentOutOfRangeException">If <see pref="value"/> is less than zero</exception>        public static bool IsPowerOfTwo(int value)        {            if (value < 0)                throw new ArgumentOutOfRangeException(nameof(value), "Must be greater than or equal to zero");            return IsPowerOfTwo((uint)value);        }         /// <summary>        /// Determines if the number is a power of 2.        /// </summary>        /// <param name="value">The value to check power of two properties</param>        /// <exception cref="ArgumentOutOfRangeException">If <see pref="value"/> is less than zero</exception>        public static bool IsPowerOfTwo(long value)        {            if (value < 0)                throw new ArgumentOutOfRangeException(nameof(value), "Must be greater than or equal to zero");            return IsPowerOfTwo((ulong)value);        }         /// <summary>        /// Determines if the number is a power of 2.        /// </summary>        /// <param name="value">The value to check power of two properties</param>        /// <returns></returns>        public static bool IsPowerOfTwo(uint value)        {            return value != 0 && ((value & (value - 1)) == 0);        }         /// <summary>        /// Determines if the number is a power of 2.        /// </summary>        /// <param name="value">The value to check power of two properties</param>        /// <returns></returns>        public static bool IsPowerOfTwo(ulong value)        {            return value != 0 && ((value & (value - 1)) == 0);        }         #endregion         #region [ Count Bits ]         /// <summary>        /// Counts the number of bits that are set        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static int CountBitsSet(uint value)        {            uint count;            for (count = 0; value > 0; value >>= 1)            {                count += value & 1;            }            return (int)count;        }         /// <summary>        /// Counts the number of bits that are set        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static int CountBitsSet(ulong value)        {            ulong count;            for (count = 0; value > 0; value >>= 1)            {                count += value & 1;            }            return (int)count;        }         /// <summary>        /// Counts the number of bits that are not set        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static int CountBitsCleared(uint value)        {            return CountBitsSet(~value);        }         /// <summary>        /// Counts the number of bits that are not set        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static int CountBitsCleared(ulong value)        {            return CountBitsSet(~value);        }         #endregion         #region [ Round To Power Of Two ]         /// <summary>        /// Rounds a number up to the nearest power of 2.        /// If the value is a power of two, the same value is returned.        /// If the value is larger than the largest power of 2. It is rounded down.        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        /// <remarks>        /// Method based on a method found at: http://graphics.stanford.edu/~seander/bithacks.htm        /// Subtitle: Round up to the next highest power of 2         /// </remarks>        public static ulong RoundUpToNearestPowerOfTwo(ulong value)        {            if (value == 0)                return 1;            if (value > (1ul << 62))                return 1ul << 63;            value--;            value |= value >> 1;            value |= value >> 2;            value |= value >> 4;            value |= value >> 8;            value |= value >> 16;            value |= value >> 32;            value++;            return value;        }         /// <summary>        /// Rounds a number up to the nearest power of 2.        /// If the value is a power of two, the same value is returned.        /// If the value is larger than the largest power of 2. It is rounded down.        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        /// <remarks>        /// Method based on a method found at: http://graphics.stanford.edu/~seander/bithacks.htm        /// Subtitle: Round up to the next highest power of 2         /// </remarks>        public static uint RoundUpToNearestPowerOfTwo(uint value)        {            if (value == 0)                return 1;            if (value > (1u << 30))                return 1u << 31;            value--;            value |= value >> 1;            value |= value >> 2;            value |= value >> 4;            value |= value >> 8;            value |= value >> 16;            value++;            return value;        }         /// <summary>        /// Rounds a number down to the nearest power of 2.        /// If the value is a power of two, the same value is returned.        /// If value is zero, one is returned.        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static ulong RoundDownToNearestPowerOfTwo(ulong value)        {            if (value == 0ul)                return 1;            return (1ul << 63) >> CountLeadingZeros(value);        }         /// <summary>        /// Rounds a number down to the nearest power of 2.        /// If the value is a power of two, the same value is returned.        /// If value is zero, 1 is returned.        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static uint RoundDownToNearestPowerOfTwo(uint value)        {            if (value == 0u)                return 1;            return (1u << 31) >> CountLeadingZeros(value);        }         #endregion         /// <summary>        /// Creates a bit mask for a number with the given number of bits.        /// </summary>        /// <param name="bitCount"></param>        /// <returns></returns>        public static ulong CreateBitMask(int bitCount)        {            if (bitCount == 0)                return 0;            return ulong.MaxValue >> (64 - bitCount);        }         #region [ Count Leading/Trailing Zeros ]         /// <summary>        /// Counts the number of consecutive 0's starting from the lowest bit working up.        /// </summary>        /// <remarks>        /// Unfortunately, c# cannot call the cpu instruction ctz        /// Example from http://en.wikipedia.org/wiki/Find_first_set        /// </remarks>        public static int CountTrailingZeros(uint value)        {            if (value == 0)                return 32;            int position = 0;            if ((value & 0xffffu) == 0u)            {                value >>= 16;                position += 16;            }            if ((value & 0xffu) == 0u)            {                value >>= 8;                position += 8;            }            if ((value & 0xfu) == 0u)            {                value >>= 4;                position += 4;            }            if ((value & 0x3u) == 0u)            {                value >>= 2;                position += 2;            }            if ((value & 0x1u) == 0u)            {                position += 1;            }            return position;        }         /// <summary>        /// Counts the number of consecutive 0's starting from the lowest bit working up.        /// </summary>        /// <remarks>        /// Unfortunately, c# cannot call the cpu instruction ctz        /// Example from http://en.wikipedia.org/wiki/Find_first_set        /// </remarks>        public static int CountTrailingZeros(ulong value)        {            if (value == 0)                return 64;            int position = 0;            if ((value & 0xfffffffful) == 0ul)            {                value >>= 32;                position += 32;            }            if ((value & 0xfffful) == 0ul)            {                value >>= 16;                position += 16;            }            if ((value & 0xfful) == 0ul)            {                value >>= 8;                position += 8;            }            if ((value & 0xful) == 0ul)            {                value >>= 4;                position += 4;            }            if ((value & 0x3ul) == 0ul)            {                value >>= 2;                position += 2;            }            if ((value & 0x1ul) == 0ul)            {                position += 1;            }            return position;        }         /// <summary>        /// Counts the number of consecutive 0's starting from the highest bit working down.        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        /// <remarks>        /// Unfortunately, c# cannot call the cpu instruction clz        /// Example from http://en.wikipedia.org/wiki/Find_first_set        /// </remarks>        public static int CountLeadingZeros(uint value)        {            if (value == 0ul)                return 32;            int position = 0;            if ((value & 0xFFFF0000u) == 0u)            {                value <<= 16;                position += 16;            }            if ((value & 0xFF000000u) == 0u)            {                value <<= 8;                position += 8;            }            if ((value & 0xF0000000) == 0u)            {                value <<= 4;                position += 4;            }            if ((value & 0xC0000000) == 0u)            {                value <<= 2;                position += 2;            }            if ((value & 0x80000000) == 0u)            {                position += 1;            }            return position;        }         /// <summary>        /// Counts the number of consecutive 0's starting from the highest bit working down.        /// </summary>        /// <remarks>        /// Unfortunately, c# cannot call the cpu instruction clz        /// Example from http://en.wikipedia.org/wiki/Find_first_set        /// </remarks>        public static int CountLeadingZeros(ulong value)        {            if (value == 0ul)                return 64;            int position = 0;            if ((value & 0xFFFFFFFF00000000ul) == 0ul)            {                value <<= 32;                position += 32;            }            if ((value & 0xFFFF000000000000ul) == 0ul)            {                value <<= 16;                position += 16;            }            if ((value & 0xFF00000000000000ul) == 0ul)            {                value <<= 8;                position += 8;            }            if ((value & 0xF000000000000000ul) == 0ul)            {                value <<= 4;                position += 4;            }            if ((value & 0xC000000000000000ul) == 0ul)            {                value <<= 2;                position += 2;            }            if ((value & 0x8000000000000000ul) == 0ul)            {                position += 1;            }            return position;        }         #endregion         #region [ Count Leading/Trailing Ones ]         /// <summary>        /// Counts the number of consecutive 1's starting from the lowest bit working up.        /// </summary>        public static int CountTrailingOnes(uint value)        {            return CountTrailingZeros(~value);        }         /// <summary>        /// Counts the number of consecutive 1's starting from the lowest bit working up.        /// </summary>        public static int CountTrailingOnes(ulong value)        {            return CountTrailingZeros(~value);        }         /// <summary>        /// Counts the number of consecutive 1's starting from the highest bit working down.        /// </summary>        public static int CountLeadingOnes(uint value)        {            return CountLeadingZeros(~value);        }         /// <summary>        /// Counts the number of consecutive 1's starting from the highest bit working down.        /// </summary>        public static int CountLeadingOnes(ulong value)        {            return CountLeadingZeros(~value);        }         #endregion         /// <summary>        /// Returns the bit position for every bit that is set in the provided value.        /// Bit positions are defined as 0-63;        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static IEnumerable<int> GetSetBitPositions(ulong value)        {            // Once value becomes zero, the remainder of the loop can be short-cut            for (int x = 0; value != 0; x++, value >>= 1)            {                if ((value & 1) == 1)                    yield return x;            }        }         /// <summary>        /// Returns the bit position for every bit that is set in the provided value.        /// Bit positions are defined as 0-31;        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static IEnumerable<int> GetSetBitPositions(uint value)        {            // Once value becomes zero, the remainder of the loop can be short-cut            for (int x = 0; value != 0; x++, value >>= 1)            {                if ((value & 1) == 1)                    yield return x;            }        }         /// <summary>        /// Returns the bit position for every bit that is cleared in the provided value.        /// Bit positions are defined as 0-31;        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static IEnumerable<int> GetClearedBitPositions(uint value)        {            return GetSetBitPositions(~value);        }         /// <summary>        /// Returns the bit position for every bit that is cleared in the provided value.        /// Bit positions are defined as 0-63;        /// </summary>        /// <param name="value"></param>        /// <returns></returns>        public static IEnumerable<int> GetClearedBitPositions(ulong value)        {            return GetSetBitPositions(~value);        }    }}