/
binary_length.jl
117 lines (94 loc) · 2.69 KB
/
binary_length.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
"""
bin_length(binNum)
Returns the length of binNum's binary representation.
# Input parameters:
- `binNum` : The number to find the binary length of.
# Examples/Tests:
```julia
bin_length(1) # returns 1
bin_length(2) # returns 2
bin_length(3) # returns 2
bin_length(4) # returns 3
bin_length(5) # returns 3
bin_length(12) # returns 4
bin_length(256) # returns 9
bin_length(1024) # returns 11
bin_length(-1) # throws DomainError
```
Contributed by: [Praneeth Jain](https://www.github.com/PraneethJain)
"""
function bin_length(binNum::T) where {T<:Integer}
binNum <= 0 && throw(DomainError("binNum must be a positive integer"))
return floor(log2(binNum)) + 1
end
"""
This algorithm features use of the OEIS entry A070939 -
length of Binary Representation of n. It finds
the length of any binary number and returns said length.
https://oeis.org/A070939
This function, as believed, is O(n)
The idea follows that the sequence is dependent on
a repeating pattern of 2. Short for sequence, seq is the
number of digits required before an increase in finNum
or final number as seen here with the first few
iterations - i on the left, final number on the right:
1 : 1
2 : 2
3 : 2
4 : 3
5 : 3
6 : 3
7 : 3
8 : 4
cont.
As you can see, for every version of i, there is an appropriate
modified number that only repeats for the sequence of the last
doubled amount.
#Contributions:
Contributed by F35H: https://github.com/F35H
"""
function bin_length_long(binNum::T) where {T<:Integer}
binNum <= 0 && throw(DomainError("binNum must be a positive integer"))
finNum = 0
seq = 1
for i in 1:binNum
if (i == seq)
finNum += 1
seq *= 2
end
end
return finNum
end
"""
This algorithm features use of the OEIS entry A070939 -
length of Binary Representation of n. It finds
the length of any binary number and returns said length.
https://oeis.org/A070939
This function, as believed, is O(log(n))
The idea follows that the sequence is dependent on
a repeating pattern of 2. The final number being finNum
increases on every doubling of i.
1 : 1
2 : 2
3 : 2
4 : 3
5 : 3
6 : 3
7 : 3
8 : 4
cont.
As you can see, for every version of i, there is an appropriate
final number that iterates on every doubling of i.
Contributors:
- [F45H](https://github.com/F35H)
"""
function bin_length_short(binNum::T) where {T<:Integer}
binNum <= 0 && throw(DomainError("binNum must be a positive integer"))
finNum = 0
i = 1
while i <= binNum
i *= 2
finNum += 1
end
return finNum
end