Line | Exclusive | Inclusive | Code |
---|---|---|---|
1 | # This file is a part of Julia. License is MIT: https://julialang.org/license | ||
2 | |||
3 | ## integer arithmetic ## | ||
4 | |||
5 | # The tuples and types that do not include 128 bit sizes are necessary to handle | ||
6 | # certain issues on 32-bit machines, and also to simplify promotion rules, as | ||
7 | # they are also used elsewhere where Int128/UInt128 support is separated out, | ||
8 | # such as in hashing2.jl | ||
9 | |||
10 | const BitSigned32_types = (Int8, Int16, Int32) | ||
11 | const BitUnsigned32_types = (UInt8, UInt16, UInt32) | ||
12 | const BitInteger32_types = (BitSigned32_types..., BitUnsigned32_types...) | ||
13 | |||
14 | const BitSigned64_types = (BitSigned32_types..., Int64) | ||
15 | const BitUnsigned64_types = (BitUnsigned32_types..., UInt64) | ||
16 | const BitInteger64_types = (BitSigned64_types..., BitUnsigned64_types...) | ||
17 | |||
18 | const BitSigned_types = (BitSigned64_types..., Int128) | ||
19 | const BitUnsigned_types = (BitUnsigned64_types..., UInt128) | ||
20 | const BitInteger_types = (BitSigned_types..., BitUnsigned_types...) | ||
21 | |||
22 | const BitSignedSmall_types = Int === Int64 ? ( Int8, Int16, Int32) : ( Int8, Int16) | ||
23 | const BitUnsignedSmall_types = Int === Int64 ? (UInt8, UInt16, UInt32) : (UInt8, UInt16) | ||
24 | const BitIntegerSmall_types = (BitSignedSmall_types..., BitUnsignedSmall_types...) | ||
25 | |||
26 | const BitSigned32 = Union{BitSigned32_types...} | ||
27 | const BitUnsigned32 = Union{BitUnsigned32_types...} | ||
28 | const BitInteger32 = Union{BitInteger32_types...} | ||
29 | |||
30 | const BitSigned64 = Union{BitSigned64_types...} | ||
31 | const BitUnsigned64 = Union{BitUnsigned64_types...} | ||
32 | const BitInteger64 = Union{BitInteger64_types...} | ||
33 | |||
34 | const BitSigned = Union{BitSigned_types...} | ||
35 | const BitUnsigned = Union{BitUnsigned_types...} | ||
36 | const BitInteger = Union{BitInteger_types...} | ||
37 | |||
38 | const BitSignedSmall = Union{BitSignedSmall_types...} | ||
39 | const BitUnsignedSmall = Union{BitUnsignedSmall_types...} | ||
40 | const BitIntegerSmall = Union{BitIntegerSmall_types...} | ||
41 | |||
42 | const BitSigned64T = Union{Type{Int8}, Type{Int16}, Type{Int32}, Type{Int64}} | ||
43 | const BitUnsigned64T = Union{Type{UInt8}, Type{UInt16}, Type{UInt32}, Type{UInt64}} | ||
44 | |||
45 | const BitIntegerType = Union{map(T->Type{T}, BitInteger_types)...} | ||
46 | |||
47 | ## integer comparisons ## | ||
48 | |||
49 | 89 (11 %) | 89 (11 %) |
89 (11 %)
samples spent in <
(<)(x::T, y::T) where {T<:BitSigned} = slt_int(x, y)
1 (1 %) (ex.), 1 (1 %) (incl.) when called from < line 338 26 (29 %) (ex.), 26 (29 %) (incl.) when called from isless line 10 53 (60 %) (ex.), 53 (60 %) (incl.) when called from isless line 16 9 (10 %) (ex.), 9 (10 %) (incl.) when called from > line 294 |
50 | |||
51 | (-)(x::BitInteger) = neg_int(x) | ||
52 | (-)(x::T, y::T) where {T<:BitInteger} = sub_int(x, y) | ||
53 | 202 (24 %) | 202 (24 %) |
202 (24 %)
samples spent in +
(+)(x::T, y::T) where {T<:BitInteger} = add_int(x, y)
9 (4 %) (ex.), 9 (4 %) (incl.) when called from sort! line 587 26 (13 %) (ex.), 26 (13 %) (incl.) when called from sort! line 594 25 (12 %) (ex.), 25 (12 %) (incl.) when called from sort! line 597 1 (0 %) (ex.), 1 (0 %) (incl.) when called from map line 180 10 (5 %) (ex.), 10 (5 %) (incl.) when called from sort! line 599 131 (65 %) (ex.), 131 (65 %) (incl.) when called from + line 529 |
54 | (*)(x::T, y::T) where {T<:BitInteger} = mul_int(x, y) | ||
55 | |||
56 | inv(x::Integer) = float(one(x)) / float(x) | ||
57 | (/)(x::T, y::T) where {T<:Integer} = float(x) / float(y) | ||
58 | # skip promotion for system integer types | ||
59 | (/)(x::BitInteger, y::BitInteger) = float(x) / float(y) | ||
60 | |||
61 | """ | ||
62 | isodd(x::Integer) -> Bool | ||
63 | |||
64 | Return `true` if `x` is odd (that is, not divisible by 2), and `false` otherwise. | ||
65 | |||
66 | # Examples | ||
67 | ```jldoctest | ||
68 | julia> isodd(9) | ||
69 | true | ||
70 | |||
71 | julia> isodd(10) | ||
72 | false | ||
73 | ``` | ||
74 | """ | ||
75 | isodd(n::Integer) = rem(n, 2) != 0 | ||
76 | |||
77 | """ | ||
78 | iseven(x::Integer) -> Bool | ||
79 | |||
80 | Return `true` is `x` is even (that is, divisible by 2), and `false` otherwise. | ||
81 | |||
82 | # Examples | ||
83 | ```jldoctest | ||
84 | julia> iseven(9) | ||
85 | false | ||
86 | |||
87 | julia> iseven(10) | ||
88 | true | ||
89 | ``` | ||
90 | """ | ||
91 | iseven(n::Integer) = !isodd(n) | ||
92 | |||
93 | signbit(x::Integer) = x < 0 | ||
94 | signbit(x::Unsigned) = false | ||
95 | |||
96 | 8 (1 %) | 8 (1 %) | flipsign(x::T, y::T) where {T<:BitSigned} = flipsign_int(x, y) |
97 | flipsign(x::BitSigned, y::BitSigned) = flipsign_int(promote(x, y)...) % typeof(x) | ||
98 | |||
99 | flipsign(x::Signed, y::Float16) = flipsign(x, bitcast(Int16, y)) | ||
100 | flipsign(x::Signed, y::Float32) = flipsign(x, bitcast(Int32, y)) | ||
101 | flipsign(x::Signed, y::Float64) = flipsign(x, bitcast(Int64, y)) | ||
102 | flipsign(x::Signed, y::Real) = flipsign(x, -oftype(x, signbit(y))) | ||
103 | |||
104 | copysign(x::Signed, y::Signed) = flipsign(x, x ⊻ y) | ||
105 | copysign(x::Signed, y::Float16) = copysign(x, bitcast(Int16, y)) | ||
106 | copysign(x::Signed, y::Float32) = copysign(x, bitcast(Int32, y)) | ||
107 | copysign(x::Signed, y::Float64) = copysign(x, bitcast(Int64, y)) | ||
108 | copysign(x::Signed, y::Real) = copysign(x, -oftype(x, signbit(y))) | ||
109 | |||
110 | """ | ||
111 | abs(x) | ||
112 | |||
113 | The absolute value of `x`. | ||
114 | |||
115 | When `abs` is applied to signed integers, overflow may occur, | ||
116 | resulting in the return of a negative value. This overflow occurs only | ||
117 | when `abs` is applied to the minimum representable value of a signed | ||
118 | integer. That is, when `x == typemin(typeof(x))`, `abs(x) == x < 0`, | ||
119 | not `-x` as might be expected. | ||
120 | |||
121 | # Examples | ||
122 | ```jldoctest | ||
123 | julia> abs(-3) | ||
124 | 3 | ||
125 | |||
126 | julia> abs(1 + im) | ||
127 | 1.4142135623730951 | ||
128 | |||
129 | julia> abs(typemin(Int64)) | ||
130 | -9223372036854775808 | ||
131 | ``` | ||
132 | """ | ||
133 | function abs end | ||
134 | |||
135 | abs(x::Unsigned) = x | ||
136 | 10 (1 %) | abs(x::Signed) = flipsign(x,x) | |
137 | |||
138 | ~(n::Integer) = -n-1 | ||
139 | |||
140 | """ | ||
141 | unsigned(x) -> Unsigned | ||
142 | |||
143 | Convert a number to an unsigned integer. If the argument is signed, it is reinterpreted as | ||
144 | unsigned without checking for negative values. | ||
145 | |||
146 | # Examples | ||
147 | ```jldoctest | ||
148 | julia> unsigned(-2) | ||
149 | 0xfffffffffffffffe | ||
150 | |||
151 | julia> unsigned(2) | ||
152 | 0x0000000000000002 | ||
153 | |||
154 | julia> signed(unsigned(-2)) | ||
155 | -2 | ||
156 | ``` | ||
157 | """ | ||
158 | unsigned(x) = x % typeof(convert(Unsigned, zero(x))) | ||
159 | unsigned(x::BitSigned) = reinterpret(typeof(convert(Unsigned, zero(x))), x) | ||
160 | |||
161 | """ | ||
162 | signed(x) | ||
163 | |||
164 | Convert a number to a signed integer. If the argument is unsigned, it is reinterpreted as | ||
165 | signed without checking for overflow. | ||
166 | """ | ||
167 | signed(x) = x % typeof(convert(Signed, zero(x))) | ||
168 | signed(x::BitUnsigned) = reinterpret(typeof(convert(Signed, zero(x))), x) | ||
169 | |||
170 | div(x::BitSigned, y::Unsigned) = flipsign(signed(div(unsigned(abs(x)), y)), x) | ||
171 | div(x::Unsigned, y::BitSigned) = unsigned(flipsign(signed(div(x, unsigned(abs(y)))), y)) | ||
172 | |||
173 | rem(x::BitSigned, y::Unsigned) = flipsign(signed(rem(unsigned(abs(x)), y)), x) | ||
174 | rem(x::Unsigned, y::BitSigned) = rem(x, unsigned(abs(y))) | ||
175 | |||
176 | function divrem(x::BitSigned, y::Unsigned) | ||
177 | q, r = divrem(unsigned(abs(x)), y) | ||
178 | flipsign(signed(q), x), flipsign(signed(r), x) | ||
179 | end | ||
180 | |||
181 | function divrem(x::Unsigned, y::BitSigned) | ||
182 | q, r = divrem(x, unsigned(abs(y))) | ||
183 | unsigned(flipsign(signed(q), y)), r | ||
184 | end | ||
185 | |||
186 | |||
187 | """ | ||
188 | mod(x, y) | ||
189 | rem(x, y, RoundDown) | ||
190 | |||
191 | The reduction of `x` modulo `y`, or equivalently, the remainder of `x` after floored | ||
192 | division by `y`, i.e. `x - y*fld(x,y)` if computed without intermediate rounding. | ||
193 | |||
194 | The result will have the same sign as `y`, and magnitude less than `abs(y)` (with some | ||
195 | exceptions, see note below). | ||
196 | |||
197 | !!! note | ||
198 | |||
199 | When used with floating point values, the exact result may not be representable by the | ||
200 | type, and so rounding error may occur. In particular, if the exact result is very | ||
201 | close to `y`, then it may be rounded to `y`. | ||
202 | |||
203 | ```jldoctest | ||
204 | julia> mod(8, 3) | ||
205 | 2 | ||
206 | |||
207 | julia> mod(9, 3) | ||
208 | 0 | ||
209 | |||
210 | julia> mod(8.9, 3) | ||
211 | 2.9000000000000004 | ||
212 | |||
213 | julia> mod(eps(), 3) | ||
214 | 2.220446049250313e-16 | ||
215 | |||
216 | julia> mod(-eps(), 3) | ||
217 | 3.0 | ||
218 | ``` | ||
219 | """ | ||
220 | function mod(x::T, y::T) where T<:Integer | ||
221 | y == -1 && return T(0) # avoid potential overflow in fld | ||
222 | return x - fld(x, y) * y | ||
223 | end | ||
224 | mod(x::BitSigned, y::Unsigned) = rem(y + unsigned(rem(x, y)), y) | ||
225 | mod(x::Unsigned, y::Signed) = rem(y + signed(rem(x, y)), y) | ||
226 | mod(x::T, y::T) where {T<:Unsigned} = rem(x, y) | ||
227 | |||
228 | # Don't promote integers for div/rem/mod since there is no danger of overflow, | ||
229 | # while there is a substantial performance penalty to 64-bit promotion. | ||
230 | div(x::T, y::T) where {T<:BitSigned64} = checked_sdiv_int(x, y) | ||
231 | rem(x::T, y::T) where {T<:BitSigned64} = checked_srem_int(x, y) | ||
232 | div(x::T, y::T) where {T<:BitUnsigned64} = checked_udiv_int(x, y) | ||
233 | rem(x::T, y::T) where {T<:BitUnsigned64} = checked_urem_int(x, y) | ||
234 | |||
235 | ## integer bitwise operations ## | ||
236 | |||
237 | """ | ||
238 | ~(x) | ||
239 | |||
240 | Bitwise not. | ||
241 | |||
242 | # Examples | ||
243 | ```jldoctest | ||
244 | julia> ~4 | ||
245 | -5 | ||
246 | |||
247 | julia> ~10 | ||
248 | -11 | ||
249 | |||
250 | julia> ~true | ||
251 | false | ||
252 | ``` | ||
253 | """ | ||
254 | (~)(x::BitInteger) = not_int(x) | ||
255 | |||
256 | """ | ||
257 | x & y | ||
258 | |||
259 | Bitwise and. Implements [three-valued logic](https://en.wikipedia.org/wiki/Three-valued_logic), | ||
260 | returning [`missing`](@ref) if one operand is `missing` and the other is `true`. | ||
261 | |||
262 | # Examples | ||
263 | ```jldoctest | ||
264 | julia> 4 & 10 | ||
265 | 0 | ||
266 | |||
267 | julia> 4 & 12 | ||
268 | 4 | ||
269 | |||
270 | julia> true & missing | ||
271 | missing | ||
272 | |||
273 | julia> false & missing | ||
274 | false | ||
275 | ``` | ||
276 | """ | ||
277 | (&)(x::T, y::T) where {T<:BitInteger} = and_int(x, y) | ||
278 | |||
279 | """ | ||
280 | x | y | ||
281 | |||
282 | Bitwise or. Implements [three-valued logic](https://en.wikipedia.org/wiki/Three-valued_logic), | ||
283 | returning [`missing`](@ref) if one operand is `missing` and the other is `false`. | ||
284 | |||
285 | # Examples | ||
286 | ```jldoctest | ||
287 | julia> 4 | 10 | ||
288 | 14 | ||
289 | |||
290 | julia> 4 | 1 | ||
291 | 5 | ||
292 | |||
293 | julia> true | missing | ||
294 | true | ||
295 | |||
296 | julia> false | missing | ||
297 | missing | ||
298 | ``` | ||
299 | """ | ||
300 | (|)(x::T, y::T) where {T<:BitInteger} = or_int(x, y) | ||
301 | xor(x::T, y::T) where {T<:BitInteger} = xor_int(x, y) | ||
302 | |||
303 | """ | ||
304 | bswap(n) | ||
305 | |||
306 | Reverse the byte order of `n`. | ||
307 | |||
308 | (See also [`ntoh`](@ref) and [`hton`](@ref) to convert between the current native byte order and big-endian order.) | ||
309 | |||
310 | # Examples | ||
311 | ```jldoctest | ||
312 | julia> a = bswap(0x10203040) | ||
313 | 0x40302010 | ||
314 | |||
315 | julia> bswap(a) | ||
316 | 0x10203040 | ||
317 | |||
318 | julia> string(1, base = 2) | ||
319 | "1" | ||
320 | |||
321 | julia> string(bswap(1), base = 2) | ||
322 | "100000000000000000000000000000000000000000000000000000000" | ||
323 | ``` | ||
324 | """ | ||
325 | bswap(x::Union{Int8, UInt8}) = x | ||
326 | bswap(x::Union{Int16, UInt16, Int32, UInt32, Int64, UInt64, Int128, UInt128}) = | ||
327 | bswap_int(x) | ||
328 | |||
329 | """ | ||
330 | count_ones(x::Integer) -> Integer | ||
331 | |||
332 | Number of ones in the binary representation of `x`. | ||
333 | |||
334 | # Examples | ||
335 | ```jldoctest | ||
336 | julia> count_ones(7) | ||
337 | 3 | ||
338 | ``` | ||
339 | """ | ||
340 | count_ones(x::BitInteger) = ctpop_int(x) % Int | ||
341 | |||
342 | """ | ||
343 | leading_zeros(x::Integer) -> Integer | ||
344 | |||
345 | Number of zeros leading the binary representation of `x`. | ||
346 | |||
347 | # Examples | ||
348 | ```jldoctest | ||
349 | julia> leading_zeros(Int32(1)) | ||
350 | 31 | ||
351 | ``` | ||
352 | """ | ||
353 | leading_zeros(x::BitInteger) = ctlz_int(x) % Int | ||
354 | |||
355 | """ | ||
356 | trailing_zeros(x::Integer) -> Integer | ||
357 | |||
358 | Number of zeros trailing the binary representation of `x`. | ||
359 | |||
360 | # Examples | ||
361 | ```jldoctest | ||
362 | julia> trailing_zeros(2) | ||
363 | 1 | ||
364 | ``` | ||
365 | """ | ||
366 | trailing_zeros(x::BitInteger) = cttz_int(x) % Int | ||
367 | |||
368 | """ | ||
369 | count_zeros(x::Integer) -> Integer | ||
370 | |||
371 | Number of zeros in the binary representation of `x`. | ||
372 | |||
373 | # Examples | ||
374 | ```jldoctest | ||
375 | julia> count_zeros(Int32(2 ^ 16 - 1)) | ||
376 | 16 | ||
377 | ``` | ||
378 | """ | ||
379 | count_zeros(x::Integer) = count_ones(~x) | ||
380 | |||
381 | """ | ||
382 | leading_ones(x::Integer) -> Integer | ||
383 | |||
384 | Number of ones leading the binary representation of `x`. | ||
385 | |||
386 | # Examples | ||
387 | ```jldoctest | ||
388 | julia> leading_ones(UInt32(2 ^ 32 - 2)) | ||
389 | 31 | ||
390 | ``` | ||
391 | """ | ||
392 | leading_ones(x::Integer) = leading_zeros(~x) | ||
393 | |||
394 | """ | ||
395 | trailing_ones(x::Integer) -> Integer | ||
396 | |||
397 | Number of ones trailing the binary representation of `x`. | ||
398 | |||
399 | # Examples | ||
400 | ```jldoctest | ||
401 | julia> trailing_ones(3) | ||
402 | 2 | ||
403 | ``` | ||
404 | """ | ||
405 | trailing_ones(x::Integer) = trailing_zeros(~x) | ||
406 | |||
407 | ## integer comparisons ## | ||
408 | |||
409 | (< )(x::T, y::T) where {T<:BitUnsigned} = ult_int(x, y) | ||
410 | 1 (0 %) | 1 (0 %) | (<=)(x::T, y::T) where {T<:BitSigned} = sle_int(x, y) |
411 | (<=)(x::T, y::T) where {T<:BitUnsigned} = ule_int(x, y) | ||
412 | |||
413 | ==(x::BitSigned, y::BitUnsigned) = (x >= 0) & (unsigned(x) == y) | ||
414 | ==(x::BitUnsigned, y::BitSigned ) = (y >= 0) & (x == unsigned(y)) | ||
415 | <( x::BitSigned, y::BitUnsigned) = (x < 0) | (unsigned(x) < y) | ||
416 | <( x::BitUnsigned, y::BitSigned ) = (y >= 0) & (x < unsigned(y)) | ||
417 | <=(x::BitSigned, y::BitUnsigned) = (x < 0) | (unsigned(x) <= y) | ||
418 | <=(x::BitUnsigned, y::BitSigned ) = (y >= 0) & (x <= unsigned(y)) | ||
419 | |||
420 | ## integer shifts ## | ||
421 | |||
422 | # unsigned shift counts always shift in the same direction | ||
423 | >>(x::BitSigned, y::BitUnsigned) = ashr_int(x, y) | ||
424 | >>(x::BitUnsigned, y::BitUnsigned) = lshr_int(x, y) | ||
425 | <<(x::BitInteger, y::BitUnsigned) = shl_int(x, y) | ||
426 | >>>(x::BitInteger, y::BitUnsigned) = lshr_int(x, y) | ||
427 | # signed shift counts can shift in either direction | ||
428 | # note: this early during bootstrap, `>=` is not yet available | ||
429 | # note: we only define Int shift counts here; the generic case is handled later | ||
430 | >>(x::BitInteger, y::Int) = | ||
431 | ifelse(0 <= y, x >> unsigned(y), x << unsigned(-y)) | ||
432 | <<(x::BitInteger, y::Int) = | ||
433 | ifelse(0 <= y, x << unsigned(y), x >> unsigned(-y)) | ||
434 | >>>(x::BitInteger, y::Int) = | ||
435 | ifelse(0 <= y, x >>> unsigned(y), x << unsigned(-y)) | ||
436 | |||
437 | for to in BitInteger_types, from in (BitInteger_types..., Bool) | ||
438 | if !(to === from) | ||
439 | if to.size < from.size | ||
440 | @eval rem(x::($from), ::Type{$to}) = trunc_int($to, x) | ||
441 | elseif from === Bool | ||
442 | @eval rem(x::($from), ::Type{$to}) = convert($to, x) | ||
443 | elseif from.size < to.size | ||
444 | if from <: Signed | ||
445 | @eval rem(x::($from), ::Type{$to}) = sext_int($to, x) | ||
446 | else | ||
447 | @eval rem(x::($from), ::Type{$to}) = convert($to, x) | ||
448 | end | ||
449 | else | ||
450 | @eval rem(x::($from), ::Type{$to}) = bitcast($to, x) | ||
451 | end | ||
452 | end | ||
453 | end | ||
454 | |||
455 | ## integer bitwise rotations ## | ||
456 | |||
457 | """ | ||
458 | bitrotate(x::Base.BitInteger, k::Integer) | ||
459 | |||
460 | `bitrotate(x, k)` implements bitwise rotation. | ||
461 | It returns the value of `x` with its bits rotated left `k` times. | ||
462 | A negative value of `k` will rotate to the right instead. | ||
463 | |||
464 | !!! compat "Julia 1.5" | ||
465 | This function requires Julia 1.5 or later. | ||
466 | |||
467 | ```jldoctest | ||
468 | julia> bitrotate(UInt8(114), 2) | ||
469 | 0xc9 | ||
470 | |||
471 | julia> bitstring(bitrotate(0b01110010, 2)) | ||
472 | "11001001" | ||
473 | |||
474 | julia> bitstring(bitrotate(0b01110010, -2)) | ||
475 | "10011100" | ||
476 | |||
477 | julia> bitstring(bitrotate(0b01110010, 8)) | ||
478 | "01110010" | ||
479 | ``` | ||
480 | """ | ||
481 | bitrotate(x::T, k::Integer) where {T <: BitInteger} = | ||
482 | (x << ((sizeof(T) << 3 - 1) & k)) | (x >>> ((sizeof(T) << 3 - 1) & -k)) | ||
483 | |||
484 | # @doc isn't available when running in Core at this point. | ||
485 | # Tuple syntax for documentation two function signatures at the same time | ||
486 | # doesn't work either at this point. | ||
487 | if nameof(@__MODULE__) === :Base | ||
488 | for fname in (:mod, :rem) | ||
489 | @eval @doc """ | ||
490 | rem(x::Integer, T::Type{<:Integer}) -> T | ||
491 | mod(x::Integer, T::Type{<:Integer}) -> T | ||
492 | %(x::Integer, T::Type{<:Integer}) -> T | ||
493 | |||
494 | Find `y::T` such that `x` ≡ `y` (mod n), where n is the number of integers representable | ||
495 | in `T`, and `y` is an integer in `[typemin(T),typemax(T)]`. | ||
496 | If `T` can represent any integer (e.g. `T == BigInt`), then this operation corresponds to | ||
497 | a conversion to `T`. | ||
498 | |||
499 | # Examples | ||
500 | ```jldoctest | ||
501 | julia> 129 % Int8 | ||
502 | -127 | ||
503 | ``` | ||
504 | """ $fname(x::Integer, T::Type{<:Integer}) | ||
505 | end | ||
506 | end | ||
507 | |||
508 | rem(x::T, ::Type{T}) where {T<:Integer} = x | ||
509 | rem(x::Integer, T::Type{<:Integer}) = convert(T, x) # `x % T` falls back to `convert` | ||
510 | rem(x::Integer, ::Type{Bool}) = ((x & 1) != 0) | ||
511 | mod(x::Integer, ::Type{T}) where {T<:Integer} = rem(x, T) | ||
512 | |||
513 | unsafe_trunc(::Type{T}, x::Integer) where {T<:Integer} = rem(x, T) | ||
514 | |||
515 | """ | ||
516 | trunc([T,] x) | ||
517 | trunc(x; digits::Integer= [, base = 10]) | ||
518 | trunc(x; sigdigits::Integer= [, base = 10]) | ||
519 | |||
520 | `trunc(x)` returns the nearest integral value of the same type as `x` whose absolute value | ||
521 | is less than or equal to `x`. | ||
522 | |||
523 | `trunc(T, x)` converts the result to type `T`, throwing an `InexactError` if the value is | ||
524 | not representable. | ||
525 | |||
526 | `digits`, `sigdigits` and `base` work as for [`round`](@ref). | ||
527 | """ | ||
528 | function trunc end | ||
529 | |||
530 | """ | ||
531 | floor([T,] x) | ||
532 | floor(x; digits::Integer= [, base = 10]) | ||
533 | floor(x; sigdigits::Integer= [, base = 10]) | ||
534 | |||
535 | `floor(x)` returns the nearest integral value of the same type as `x` that is less than or | ||
536 | equal to `x`. | ||
537 | |||
538 | `floor(T, x)` converts the result to type `T`, throwing an `InexactError` if the value is | ||
539 | not representable. | ||
540 | |||
541 | `digits`, `sigdigits` and `base` work as for [`round`](@ref). | ||
542 | """ | ||
543 | function floor end | ||
544 | |||
545 | """ | ||
546 | ceil([T,] x) | ||
547 | ceil(x; digits::Integer= [, base = 10]) | ||
548 | ceil(x; sigdigits::Integer= [, base = 10]) | ||
549 | |||
550 | `ceil(x)` returns the nearest integral value of the same type as `x` that is greater than or | ||
551 | equal to `x`. | ||
552 | |||
553 | `ceil(T, x)` converts the result to type `T`, throwing an `InexactError` if the value is not | ||
554 | representable. | ||
555 | |||
556 | `digits`, `sigdigits` and `base` work as for [`round`](@ref). | ||
557 | """ | ||
558 | function ceil end | ||
559 | |||
560 | round(::Type{T}, x::Integer) where {T<:Integer} = convert(T, x) | ||
561 | trunc(::Type{T}, x::Integer) where {T<:Integer} = convert(T, x) | ||
562 | floor(::Type{T}, x::Integer) where {T<:Integer} = convert(T, x) | ||
563 | ceil(::Type{T}, x::Integer) where {T<:Integer} = convert(T, x) | ||
564 | |||
565 | ## integer construction ## | ||
566 | |||
567 | """ | ||
568 | @int128_str str | ||
569 | @int128_str(str) | ||
570 | |||
571 | `@int128_str` parses a string into a Int128 | ||
572 | Throws an `ArgumentError` if the string is not a valid integer | ||
573 | """ | ||
574 | macro int128_str(s) | ||
575 | return parse(Int128, s) | ||
576 | end | ||
577 | |||
578 | """ | ||
579 | @uint128_str str | ||
580 | @uint128_str(str) | ||
581 | |||
582 | `@uint128_str` parses a string into a UInt128 | ||
583 | Throws an `ArgumentError` if the string is not a valid integer | ||
584 | """ | ||
585 | macro uint128_str(s) | ||
586 | return parse(UInt128, s) | ||
587 | end | ||
588 | |||
589 | """ | ||
590 | @big_str str | ||
591 | @big_str(str) | ||
592 | |||
593 | Parse a string into a [`BigInt`](@ref) or [`BigFloat`](@ref), | ||
594 | and throw an `ArgumentError` if the string is not a valid number. | ||
595 | For integers `_` is allowed in the string as a separator. | ||
596 | |||
597 | # Examples | ||
598 | ```jldoctest | ||
599 | julia> big"123_456" | ||
600 | 123456 | ||
601 | |||
602 | julia> big"7891.5" | ||
603 | 7891.5 | ||
604 | ``` | ||
605 | """ | ||
606 | macro big_str(s) | ||
607 | if '_' in s | ||
608 | # remove _ in s[2:end-1] | ||
609 | bf = IOBuffer(maxsize=lastindex(s)) | ||
610 | print(bf, s[1]) | ||
611 | for c in SubString(s, 2, lastindex(s)-1) | ||
612 | c != '_' && print(bf, c) | ||
613 | end | ||
614 | print(bf, s[end]) | ||
615 | seekstart(bf) | ||
616 | n = tryparse(BigInt, String(take!(bf))) | ||
617 | n === nothing || return n | ||
618 | else | ||
619 | n = tryparse(BigInt, s) | ||
620 | n === nothing || return n | ||
621 | n = tryparse(BigFloat, s) | ||
622 | n === nothing || return n | ||
623 | end | ||
624 | message = "invalid number format $s for BigInt or BigFloat" | ||
625 | return :(throw(ArgumentError($message))) | ||
626 | end | ||
627 | |||
628 | ## integer promotions ## | ||
629 | |||
630 | # with different sizes, promote to larger type | ||
631 | promote_rule(::Type{Int16}, ::Union{Type{Int8}, Type{UInt8}}) = Int16 | ||
632 | promote_rule(::Type{Int32}, ::Union{Type{Int16}, Type{Int8}, Type{UInt16}, Type{UInt8}}) = Int32 | ||
633 | promote_rule(::Type{Int64}, ::Union{Type{Int16}, Type{Int32}, Type{Int8}, Type{UInt16}, Type{UInt32}, Type{UInt8}}) = Int64 | ||
634 | promote_rule(::Type{Int128}, ::Union{Type{Int16}, Type{Int32}, Type{Int64}, Type{Int8}, Type{UInt16}, Type{UInt32}, Type{UInt64}, Type{UInt8}}) = Int128 | ||
635 | promote_rule(::Type{UInt16}, ::Union{Type{Int8}, Type{UInt8}}) = UInt16 | ||
636 | promote_rule(::Type{UInt32}, ::Union{Type{Int16}, Type{Int8}, Type{UInt16}, Type{UInt8}}) = UInt32 | ||
637 | promote_rule(::Type{UInt64}, ::Union{Type{Int16}, Type{Int32}, Type{Int8}, Type{UInt16}, Type{UInt32}, Type{UInt8}}) = UInt64 | ||
638 | promote_rule(::Type{UInt128}, ::Union{Type{Int16}, Type{Int32}, Type{Int64}, Type{Int8}, Type{UInt16}, Type{UInt32}, Type{UInt64}, Type{UInt8}}) = UInt128 | ||
639 | # with mixed signedness and same size, Unsigned wins | ||
640 | promote_rule(::Type{UInt8}, ::Type{Int8} ) = UInt8 | ||
641 | promote_rule(::Type{UInt16}, ::Type{Int16} ) = UInt16 | ||
642 | promote_rule(::Type{UInt32}, ::Type{Int32} ) = UInt32 | ||
643 | promote_rule(::Type{UInt64}, ::Type{Int64} ) = UInt64 | ||
644 | promote_rule(::Type{UInt128}, ::Type{Int128}) = UInt128 | ||
645 | |||
646 | ## traits ## | ||
647 | |||
648 | """ | ||
649 | typemin(T) | ||
650 | |||
651 | The lowest value representable by the given (real) numeric DataType `T`. | ||
652 | |||
653 | # Examples | ||
654 | ```jldoctest | ||
655 | julia> typemin(Float16) | ||
656 | -Inf16 | ||
657 | |||
658 | julia> typemin(Float32) | ||
659 | -Inf32 | ||
660 | ``` | ||
661 | """ | ||
662 | function typemin end | ||
663 | |||
664 | """ | ||
665 | typemax(T) | ||
666 | |||
667 | The highest value representable by the given (real) numeric `DataType`. | ||
668 | |||
669 | # Examples | ||
670 | ```jldoctest | ||
671 | julia> typemax(Int8) | ||
672 | 127 | ||
673 | |||
674 | julia> typemax(UInt32) | ||
675 | 0xffffffff | ||
676 | ``` | ||
677 | """ | ||
678 | function typemax end | ||
679 | |||
680 | typemin(::Type{Int8 }) = Int8(-128) | ||
681 | typemax(::Type{Int8 }) = Int8(127) | ||
682 | typemin(::Type{UInt8 }) = UInt8(0) | ||
683 | typemax(::Type{UInt8 }) = UInt8(255) | ||
684 | typemin(::Type{Int16 }) = Int16(-32768) | ||
685 | typemax(::Type{Int16 }) = Int16(32767) | ||
686 | typemin(::Type{UInt16}) = UInt16(0) | ||
687 | typemax(::Type{UInt16}) = UInt16(65535) | ||
688 | typemin(::Type{Int32 }) = Int32(-2147483648) | ||
689 | typemax(::Type{Int32 }) = Int32(2147483647) | ||
690 | typemin(::Type{UInt32}) = UInt32(0) | ||
691 | typemax(::Type{UInt32}) = UInt32(4294967295) | ||
692 | typemin(::Type{Int64 }) = -9223372036854775808 | ||
693 | typemax(::Type{Int64 }) = 9223372036854775807 | ||
694 | typemin(::Type{UInt64}) = UInt64(0) | ||
695 | typemax(::Type{UInt64}) = 0xffffffffffffffff | ||
696 | @eval typemin(::Type{UInt128}) = $(convert(UInt128, 0)) | ||
697 | @eval typemax(::Type{UInt128}) = $(bitcast(UInt128, convert(Int128, -1))) | ||
698 | @eval typemin(::Type{Int128} ) = $(convert(Int128, 1) << 127) | ||
699 | @eval typemax(::Type{Int128} ) = $(bitcast(Int128, typemax(UInt128) >> 1)) | ||
700 | |||
701 | |||
702 | widen(::Type{Int8}) = Int16 | ||
703 | widen(::Type{Int16}) = Int32 | ||
704 | widen(::Type{Int32}) = Int64 | ||
705 | widen(::Type{Int64}) = Int128 | ||
706 | widen(::Type{UInt8}) = UInt16 | ||
707 | widen(::Type{UInt16}) = UInt32 | ||
708 | widen(::Type{UInt32}) = UInt64 | ||
709 | widen(::Type{UInt64}) = UInt128 | ||
710 | |||
711 | # a few special cases, | ||
712 | # Int64*UInt64 => Int128 | ||
713 | # |x|<=2^(k-1), |y|<=2^k-1 => |x*y|<=2^(2k-1)-1 | ||
714 | widemul(x::Signed,y::Unsigned) = widen(x) * signed(widen(y)) | ||
715 | widemul(x::Unsigned,y::Signed) = signed(widen(x)) * widen(y) | ||
716 | # multplication by Bool doesn't require widening | ||
717 | widemul(x::Bool,y::Bool) = x * y | ||
718 | widemul(x::Bool,y::Number) = x * y | ||
719 | widemul(x::Number,y::Bool) = x * y | ||
720 | |||
721 | |||
722 | ## wide multiplication, Int128 multiply and divide ## | ||
723 | |||
724 | if Core.sizeof(Int) == 4 | ||
725 | function widemul(u::Int64, v::Int64) | ||
726 | local u0::UInt64, v0::UInt64, w0::UInt64 | ||
727 | local u1::Int64, v1::Int64, w1::UInt64, w2::Int64, t::UInt64 | ||
728 | |||
729 | u0 = u & 0xffffffff; u1 = u >> 32 | ||
730 | v0 = v & 0xffffffff; v1 = v >> 32 | ||
731 | w0 = u0 * v0 | ||
732 | t = reinterpret(UInt64, u1) * v0 + (w0 >>> 32) | ||
733 | w2 = reinterpret(Int64, t) >> 32 | ||
734 | w1 = u0 * reinterpret(UInt64, v1) + (t & 0xffffffff) | ||
735 | hi = u1 * v1 + w2 + (reinterpret(Int64, w1) >> 32) | ||
736 | lo = w0 & 0xffffffff + (w1 << 32) | ||
737 | return Int128(hi) << 64 + Int128(lo) | ||
738 | end | ||
739 | |||
740 | function widemul(u::UInt64, v::UInt64) | ||
741 | local u0::UInt64, v0::UInt64, w0::UInt64 | ||
742 | local u1::UInt64, v1::UInt64, w1::UInt64, w2::UInt64, t::UInt64 | ||
743 | |||
744 | u0 = u & 0xffffffff; u1 = u >>> 32 | ||
745 | v0 = v & 0xffffffff; v1 = v >>> 32 | ||
746 | w0 = u0 * v0 | ||
747 | t = u1 * v0 + (w0 >>> 32) | ||
748 | w2 = t >>> 32 | ||
749 | w1 = u0 * v1 + (t & 0xffffffff) | ||
750 | hi = u1 * v1 + w2 + (w1 >>> 32) | ||
751 | lo = w0 & 0xffffffff + (w1 << 32) | ||
752 | return UInt128(hi) << 64 + UInt128(lo) | ||
753 | end | ||
754 | |||
755 | function *(u::Int128, v::Int128) | ||
756 | u0 = u % UInt64; u1 = Int64(u >> 64) | ||
757 | v0 = v % UInt64; v1 = Int64(v >> 64) | ||
758 | lolo = widemul(u0, v0) | ||
759 | lohi = widemul(reinterpret(Int64, u0), v1) | ||
760 | hilo = widemul(u1, reinterpret(Int64, v0)) | ||
761 | t = reinterpret(UInt128, hilo) + (lolo >>> 64) | ||
762 | w1 = reinterpret(UInt128, lohi) + (t & 0xffffffffffffffff) | ||
763 | return Int128(lolo & 0xffffffffffffffff) + reinterpret(Int128, w1) << 64 | ||
764 | end | ||
765 | |||
766 | function *(u::UInt128, v::UInt128) | ||
767 | u0 = u % UInt64; u1 = UInt64(u>>>64) | ||
768 | v0 = v % UInt64; v1 = UInt64(v>>>64) | ||
769 | lolo = widemul(u0, v0) | ||
770 | lohi = widemul(u0, v1) | ||
771 | hilo = widemul(u1, v0) | ||
772 | t = hilo + (lolo >>> 64) | ||
773 | w1 = lohi + (t & 0xffffffffffffffff) | ||
774 | return (lolo & 0xffffffffffffffff) + UInt128(w1) << 64 | ||
775 | end | ||
776 | |||
777 | function _setbit(x::UInt128, i) | ||
778 | # faster version of `return x | (UInt128(1) << i)` | ||
779 | j = i >> 5 | ||
780 | y = UInt128(one(UInt32) << (i & 0x1f)) | ||
781 | if j == 0 | ||
782 | return x | y | ||
783 | elseif j == 1 | ||
784 | return x | (y << 32) | ||
785 | elseif j == 2 | ||
786 | return x | (y << 64) | ||
787 | elseif j == 3 | ||
788 | return x | (y << 96) | ||
789 | end | ||
790 | return x | ||
791 | end | ||
792 | |||
793 | function divrem(x::UInt128, y::UInt128) | ||
794 | iszero(y) && throw(DivideError()) | ||
795 | if (x >> 64) % UInt64 == 0 | ||
796 | if (y >> 64) % UInt64 == 0 | ||
797 | # fast path: upper 64 bits are zero, so we can fallback to UInt64 division | ||
798 | q64, x64 = divrem(x % UInt64, y % UInt64) | ||
799 | return UInt128(q64), UInt128(x64) | ||
800 | else | ||
801 | # this implies y>x, so | ||
802 | return zero(UInt128), x | ||
803 | end | ||
804 | end | ||
805 | n = leading_zeros(y) - leading_zeros(x) | ||
806 | q = zero(UInt128) | ||
807 | ys = y << n | ||
808 | while n >= 0 | ||
809 | # ys == y * 2^n | ||
810 | if ys <= x | ||
811 | x -= ys | ||
812 | q = _setbit(q, n) | ||
813 | if (x >> 64) % UInt64 == 0 | ||
814 | # exit early, similar to above fast path | ||
815 | if (y >> 64) % UInt64 == 0 | ||
816 | q64, x64 = divrem(x % UInt64, y % UInt64) | ||
817 | q |= q64 | ||
818 | x = UInt128(x64) | ||
819 | end | ||
820 | return q, x | ||
821 | end | ||
822 | end | ||
823 | ys >>>= 1 | ||
824 | n -= 1 | ||
825 | end | ||
826 | return q, x | ||
827 | end | ||
828 | |||
829 | function div(x::Int128, y::Int128) | ||
830 | (x == typemin(Int128)) & (y == -1) && throw(DivideError()) | ||
831 | return Int128(div(BigInt(x), BigInt(y)))::Int128 | ||
832 | end | ||
833 | div(x::UInt128, y::UInt128) = divrem(x, y)[1] | ||
834 | |||
835 | function rem(x::Int128, y::Int128) | ||
836 | return Int128(rem(BigInt(x), BigInt(y)))::Int128 | ||
837 | end | ||
838 | |||
839 | function rem(x::UInt128, y::UInt128) | ||
840 | iszero(y) && throw(DivideError()) | ||
841 | if (x >> 64) % UInt64 == 0 | ||
842 | if (y >> 64) % UInt64 == 0 | ||
843 | # fast path: upper 64 bits are zero, so we can fallback to UInt64 division | ||
844 | return UInt128(rem(x % UInt64, y % UInt64)) | ||
845 | else | ||
846 | # this implies y>x, so | ||
847 | return x | ||
848 | end | ||
849 | end | ||
850 | n = leading_zeros(y) - leading_zeros(x) | ||
851 | ys = y << n | ||
852 | while n >= 0 | ||
853 | # ys == y * 2^n | ||
854 | if ys <= x | ||
855 | x -= ys | ||
856 | if (x >> 64) % UInt64 == 0 | ||
857 | # exit early, similar to above fast path | ||
858 | if (y >> 64) % UInt64 == 0 | ||
859 | x = UInt128(rem(x % UInt64, y % UInt64)) | ||
860 | end | ||
861 | return x | ||
862 | end | ||
863 | end | ||
864 | ys >>>= 1 | ||
865 | n -= 1 | ||
866 | end | ||
867 | return x | ||
868 | end | ||
869 | |||
870 | function mod(x::Int128, y::Int128) | ||
871 | return Int128(mod(BigInt(x), BigInt(y)))::Int128 | ||
872 | end | ||
873 | else | ||
874 | *(x::T, y::T) where {T<:Union{Int128,UInt128}} = mul_int(x, y) | ||
875 | |||
876 | div(x::Int128, y::Int128) = checked_sdiv_int(x, y) | ||
877 | div(x::UInt128, y::UInt128) = checked_udiv_int(x, y) | ||
878 | |||
879 | rem(x::Int128, y::Int128) = checked_srem_int(x, y) | ||
880 | rem(x::UInt128, y::UInt128) = checked_urem_int(x, y) | ||
881 | end | ||
882 | |||
883 | # issue #15489: since integer ops are unchecked, they shouldn't check promotion | ||
884 | for op in (:+, :-, :*, :&, :|, :xor) | ||
885 | @eval function $op(a::Integer, b::Integer) | ||
886 | T = promote_typeof(a, b) | ||
887 | aT, bT = a % T, b % T | ||
888 | not_sametype((a, b), (aT, bT)) | ||
889 | return $op(aT, bT) | ||
890 | end | ||
891 | end | ||
892 | |||
893 | const _mask1_uint128 = (UInt128(0x5555555555555555) << 64) | UInt128(0x5555555555555555) | ||
894 | const _mask2_uint128 = (UInt128(0x3333333333333333) << 64) | UInt128(0x3333333333333333) | ||
895 | const _mask4_uint128 = (UInt128(0x0f0f0f0f0f0f0f0f) << 64) | UInt128(0x0f0f0f0f0f0f0f0f) | ||
896 | |||
897 | """ | ||
898 | bitreverse(x) | ||
899 | |||
900 | Reverse the order of bits in integer `x`. `x` must have a fixed bit width, | ||
901 | e.g. be an `Int16` or `Int32`. | ||
902 | |||
903 | !!! compat "Julia 1.5" | ||
904 | This function requires Julia 1.5 or later. | ||
905 | |||
906 | # Examples | ||
907 | ```jldoctest | ||
908 | julia> bitreverse(0x8080808080808080) | ||
909 | 0x0101010101010101 | ||
910 | |||
911 | julia> reverse(bitstring(0xa06e)) == bitstring(bitreverse(0xa06e)) | ||
912 | true | ||
913 | ``` | ||
914 | """ | ||
915 | function bitreverse(x::BitInteger) | ||
916 | # TODO: consider using llvm.bitreverse intrinsic | ||
917 | z = unsigned(x) | ||
918 | mask1 = _mask1_uint128 % typeof(z) | ||
919 | mask2 = _mask2_uint128 % typeof(z) | ||
920 | mask4 = _mask4_uint128 % typeof(z) | ||
921 | z = ((z & mask1) << 1) | ((z >> 1) & mask1) | ||
922 | z = ((z & mask2) << 2) | ((z >> 2) & mask2) | ||
923 | z = ((z & mask4) << 4) | ((z >> 4) & mask4) | ||
924 | return bswap(z) % typeof(x) | ||
925 | end |