StatProfilerHTML - /home/tkluck/src/julia/usr/bin/../share/julia/base/./int.jl

File source code

Line

Exclusive

Inclusive

Code

# This file is a part of Julia. License is MIT: https://julialang.org/license

## integer arithmetic ##

# The tuples and types that do not include 128 bit sizes are necessary to handle

# certain issues on 32-bit machines, and also to simplify promotion rules, as

# they are also used elsewhere where Int128/UInt128 support is separated out,

# such as in hashing2.jl

const BitSigned32_types = (Int8, Int16, Int32)

const BitUnsigned32_types = (UInt8, UInt16, UInt32)

const BitInteger32_types = (BitSigned32_types..., BitUnsigned32_types...)

const BitSigned64_types = (BitSigned32_types..., Int64)

const BitUnsigned64_types = (BitUnsigned32_types..., UInt64)

const BitInteger64_types = (BitSigned64_types..., BitUnsigned64_types...)

const BitSigned_types = (BitSigned64_types..., Int128)

const BitUnsigned_types = (BitUnsigned64_types..., UInt128)

const BitInteger_types = (BitSigned_types..., BitUnsigned_types...)

const BitSignedSmall_types = Int === Int64 ? ( Int8, Int16, Int32) : ( Int8, Int16)

const BitUnsignedSmall_types = Int === Int64 ? (UInt8, UInt16, UInt32) : (UInt8, UInt16)

const BitIntegerSmall_types = (BitSignedSmall_types..., BitUnsignedSmall_types...)

const BitSigned32 = Union{BitSigned32_types...}

const BitUnsigned32 = Union{BitUnsigned32_types...}

const BitInteger32 = Union{BitInteger32_types...}

const BitSigned64 = Union{BitSigned64_types...}

const BitUnsigned64 = Union{BitUnsigned64_types...}

const BitInteger64 = Union{BitInteger64_types...}

const BitSigned = Union{BitSigned_types...}

const BitUnsigned = Union{BitUnsigned_types...}

const BitInteger = Union{BitInteger_types...}

const BitSignedSmall = Union{BitSignedSmall_types...}

const BitUnsignedSmall = Union{BitUnsignedSmall_types...}

const BitIntegerSmall = Union{BitIntegerSmall_types...}

const BitSigned64T = Union{Type{Int8}, Type{Int16}, Type{Int32}, Type{Int64}}

const BitUnsigned64T = Union{Type{UInt8}, Type{UInt16}, Type{UInt32}, Type{UInt64}}

const BitIntegerType = Union{map(T->Type{T}, BitInteger_types)...}

## integer comparisons ##

89 (11 %)

89 (11 %) samples spent in <
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

(<)(x::T, y::T) where {T<:BitSigned} = slt_int(x, y)

(-)(x::BitInteger) = neg_int(x)

(-)(x::T, y::T) where {T<:BitInteger} = sub_int(x, y)

202 (24 %)

202 (24 %) samples spent in +
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

(+)(x::T, y::T) where {T<:BitInteger} = add_int(x, y)

(*)(x::T, y::T) where {T<:BitInteger} = mul_int(x, y)

inv(x::Integer) = float(one(x)) / float(x)

(/)(x::T, y::T) where {T<:Integer} = float(x) / float(y)

# skip promotion for system integer types

(/)(x::BitInteger, y::BitInteger) = float(x) / float(y)

"""

isodd(x::Integer) -> Bool

Return `true` if `x` is odd (that is, not divisible by 2), and `false` otherwise.

# Examples

```jldoctest

julia> isodd(9)

true

julia> isodd(10)

false

```

"""

isodd(n::Integer) = rem(n, 2) != 0

"""

iseven(x::Integer) -> Bool

Return `true` is `x` is even (that is, divisible by 2), and `false` otherwise.

# Examples

```jldoctest

julia> iseven(9)

false

julia> iseven(10)

true

```

"""

iseven(n::Integer) = !isodd(n)

signbit(x::Integer) = x < 0

signbit(x::Unsigned) = false

8 (1 %)

8 (1 %) samples spent in flipsign
8 (100 %) (ex.), 8 (100 %) (incl.) when called from abs line 136

flipsign(x::T, y::T) where {T<:BitSigned} = flipsign_int(x, y)

flipsign(x::BitSigned, y::BitSigned) = flipsign_int(promote(x, y)...) % typeof(x)

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

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 %)

10 (1 %) samples spent in abs
10 (100 %) (incl.) when called from isless line 10

2 (20 %) samples spent calling flipsign
8 (80 %) samples spent calling flipsign

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

206

207

julia> mod(9, 3)

208

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

266

267

julia> 4 & 12

268

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

289

290

julia> 4 | 1

291

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

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

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

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

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

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

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 %) samples spent in <=
1 (100 %) (ex.), 1 (100 %) (incl.) when called from sort! line 584

(<=)(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