Documentation
¶
Overview ¶
Package binary describes algorithms that use binary operations for different calculations.
Index ¶
- func Abs(base, n int) int
- func BitCounter(n uint) int
- func FastInverseSqrt(number float32) float32
- func IsPowerOfTwo(x int) bool
- func IsPowerOfTwoLeftShift(number uint) bool
- func LogBase2(n uint32) uint32
- func MeanUsingAndXor(a int, b int) int
- func MeanUsingRightShift(a int, b int) int
- func ReverseBits(number uint) uint
- func SequenceGrayCode(n uint) []uint
- func Sqrt(n float32) float32
- func XorSearchMissingNumber(a []int) int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Abs ¶
Abs returns absolute value using binary operation Principle of operation: 1) Get the mask by right shift by the base 2) Base is the size of an integer variable in bits, for example, for int32 it will be 32, for int64 it will be 64 3) For negative numbers, above step sets mask as 1 1 1 1 1 1 1 1 and 0 0 0 0 0 0 0 0 for positive numbers. 4) Add the mask to the given number. 5) XOR of mask + n and mask gives the absolute value.
func BitCounter ¶
BitCounter - The function returns the number of set bits for an unsigned integer number
func FastInverseSqrt ¶
FastInverseSqrt assumes that argument is always positive, and it does not deal with negative numbers. The "magic" number 0x5f3759df is hex for 1597463007 in decimals. The math.Float32bits is alias to *(*uint32)(unsafe.Pointer(&f)) and math.Float32frombits is to *(*float32)(unsafe.Pointer(&b)).
func IsPowerOfTwo ¶
IsPowerOfTwo This function uses the fact that powers of 2 are represented like 10...0 in binary, and numbers one less than the power of 2 are represented like 11...1. Therefore, using the and function:
10...0 & 01...1 00...0 -> 0
This is also true for 0, which is not a power of 2, for which we have to add and extra condition.
func IsPowerOfTwoLeftShift ¶
IsPowerOfTwoLeftShift This function takes advantage of the fact that left shifting a number by 1 is equivalent to multiplying by 2. For example, binary 00000001 when shifted by 3 becomes 00001000, which in decimal system is 8 or = 2 * 2 * 2
func LogBase2 ¶
LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) [See more](https://en.wikipedia.org/wiki/Logarithm)
func MeanUsingAndXor ¶
MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operations
func MeanUsingRightShift ¶
MeanUsingRightShift This function finds arithmetic mean using right shift
func ReverseBits ¶
ReverseBits This function initialized the result by 0 (all bits 0) and process the given number starting from its least significant bit. If the current bit is 1, set the corresponding most significant bit in the result and finally move on to the next bit in the input number. Repeat this till all its bits are processed.
func SequenceGrayCode ¶
SequenceGrayCode The function generates an "Gray code" sequence of length n
func XorSearchMissingNumber ¶
XorSearchMissingNumber This function finds a missing number in a sequence
Types ¶
This section is empty.
Source Files