CS61B Lecture #14: Integers
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 1
Type Bits Signed?
Copyright By PowCoder代写 加微信 powcoder
Literals Cast from int: (byte) 3
Integer Types and Literals
short None. Cast from int: (short) 4096
long 64 Yes
’a’ // (char) 97
’\n’ // newline ((char) 10)
’\t’ // tab ((char) 8)
’\\’ // backslash
’A’, ’\101’, ’\u0041’ // == (char) 65 123
0100 // Octal for 64
0x3f, 0xffffffff // Hexadecimal 63, -1 (!) 123L, 01000L, 0x3fL
1234567891011L
• Negative numerals are just negated (positive) literals.
• “N bits” means that there are 2N integers in the domain of the type:
– If signed, range of values is −2N−1 .. 2N−1 − 1.
– If unsigned, only non-negative numbers, and range is 0..2N − 1.
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 2
• Problem: How do we handle overflow, such as occurs in 10000*10000*10000?
• Some languages throw an exception (Ada), some give undefined re- sults (C, C++)
• Java defines the result of any arithmetic operation or conversion on integer types to “wrap around”—modular arithmetic.
• That is, the “next number” after the largest in an integer type is the smallest (like “clock arithmetic”).
• E.g., (byte) 128 == (byte) (127+1) == (byte) -128
• In general,
– If the result of some arithmetic subexpression is supposed to have type T , an n-bit integer type,
– then we compute the real (mathematical) value, x,
–and yield a number, x′, that is in the range of T, and that is
equivalent to x modulo 2n.
– (That means that x − x′ is a multiple of 2n.)
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 3
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 4
a′ +b′′ (a′ −b′)′ (a′·b′)′ (ak )′
= (a′ +b)′ =a+b′
= (a′ +(−b)′)′ =(a−b)′ =a′·b′=a·b′
= ((a′)k)′ = (a · (ak−1)′)′, for k > 0.
Modular Arithmetic
•Definea≡b(mod n)tomeanthata−b=knforsomeintegerk.
• Define the binary operation a mod n as the value b such that a ≡ b (mod n) and0≤b
we won’t bother with that here.) This is not the same as Java’s % operation.
• Various facts: (Here, let a′ denote a mod n).
Modular Arithmetic: Examples
• (byte) (64*8) yields 0, since 512 − 0 = 2 × 28.
• (byte) (64*2) and (byte) (127+1) yield -128, since 128 − (−128) =
• (byte) (101*99) yields 15, since 9999 − 15 = 39 × ·28.
• (byte) (-30*13) yields 122, since −390 − 122 = −2 × 28.
• (char) (-1) yields 216 − 1, since −1 − (216 − 1) = −1 × 216.
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 5
Modular Arithmetic and Bits
• Why wrap around?
• Java’s definition is the natural one for a machine that uses binary
arithmetic.
• For example, consider bytes (8 bits):
1100101 1100011
100111|00001111 100111|00000000 00001111
ples of 28 = 256.
• So throwing them away is the same as arithmetic modulo 256.
9999 − 9984 15
from 0 at the right, corresponds to 2n.
• In general, bit n, counting
• The bits to the left of the vertical bars therefore represent multi-
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 6
Negative numbers
• Why this representation for -1?
1 000000012 + −1 111111112 = 0 1|000000002
Only 8 bits in a byte, so bit 8 falls off, leaving 0.
• The truncated bit is in the 28 place, so throwing it away gives an
equal number modulo 28. All bits to the left of it are also divisible by 28.
• On unsigned types (char), arithmetic is the same, but we choose to represent only non-negative numbers modulo 216:
1 00000000000000012 + 216 − 1 11111111111111112 = 216 + 0 1|00000000000000002
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 7
Conversion
• In general Java will silently convert from one type to another if this makes sense and no information is lost from value.
• Otherwise, cast explicitly, as in (byte) x. • Hence, given
byte aByte; char aChar; short aShort; int anInt; long aLong;
aShort = aByte; anInt = aByte; anInt = aShort; anInt = aChar; aLong = anInt;
// Not OK, might lose information:
anInt = aLong; aByte = anInt; aChar = anInt; aShort = anInt; aShort = aChar; aChar = aShort; aChar = aByte;
// OK by special dispensation:
aByte = 13; // 13 is compile-time constant aByte = 12+100 // 112 is compile-time constant
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 8
• Arithmetic operations (+, *, . . . ) promote operands as needed. • Promotion is just implicit conversion.
• For integer operations,
– if any operand is long, promote both to long. – otherwise promote both to int.
aByte + 3 == (int) aByte + 3 // Type int aLong + 3 == aLong + (long) 3 // Type long
’A’ + 2 == (int) ’A’ + 2 // Type int aByte = aByte + 1 // ILLEGAL (why?)
• But fortunately,
aByte += 1; // Defined as aByte = (byte) (aByte+1)
• Common example:
// Assume aChar is an upper-case letter
char lowerCaseChar = (char) (’a’ + aChar – ’A’); // why cast? Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 9
Bit twiddling
• Java (and C, C++) allow for handling integer types as sequences of bits. No “conversion to bits” needed: they already are.
• Operations and their uses:
Mask Set Flip Flip all
00101100 00101100 00101100
& 10100111 | 10100111 ^ 10100111 ~ 10100111
00100100 10101111 10001011 01011000
• Shifting:
10101101 << 3
Arithmetic Right
10101101 >> 3
Logical Right
10101100 >>> 3
• What is:
(-1) >>> 29?
(x >>> 3) & ((1<<5)-1)?
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 10
Bit twiddling
• Java (and C, C++) allow for handling integer types as sequences of bits. No “conversion to bits” needed: they already are.
• Operations and their uses:
Mask Set Flip Flip all
00101100 00101100 00101100
& 10100111 | 10100111 ^ 10100111 ~ 10100111
00100100 10101111 10001011 01011000
• Shifting:
10101101 << 3
Arithmetic Right
10101101 >> 3
Logical Right
10101100 >>> 3
• What is:
(-1) >>> 29?
(x >>> 3) & ((1<<5)-1)?
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 11
Bit twiddling
• Java (and C, C++) allow for handling integer types as sequences of bits. No “conversion to bits” needed: they already are.
• Operations and their uses:
Mask Set Flip Flip all
00101100 00101100 00101100
& 10100111 | 10100111 ^ 10100111 ~ 10100111
00100100 10101111 10001011 01011000
• Shifting:
10101101 << 3
Arithmetic Right
10101101 >> 3
Logical Right
10101100 >>> 3
• What is:
(-1) >>> 29?
(x >>> 3) & ((1<<5)-1)?
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 12
Bit twiddling
• Java (and C, C++) allow for handling integer types as sequences of bits. No “conversion to bits” needed: they already are.
• Operations and their uses:
Mask Set Flip Flip all
00101100 00101100 00101100
& 10100111 | 10100111 ^ 10100111 ~ 10100111
00100100 10101111 10001011 01011000
• Shifting:
10101101 << 3
Arithmetic Right
10101101 >> 3
Logical Right
10101100 >>> 3
• What is:
(-1) >>> 29?
(x >>> 3) & ((1<<5)-1)?
= ⌊x/2n⌋ (i.e., rounded down).
Last modified: Mon Sep 30 16:56:19 2019
CS61B: Lecture #14 13
Bit twiddling
• Java (and C, C++) allow for handling integer types as sequences of bits. No “conversion to bits” needed: they already are.
• Operations and their uses:
Mask Set Flip Flip all
00101100 00101100 00101100
& 10100111 | 10100111 ^ 10100111 ~ 10100111
00100100 10101111 10001011 01011000
• Shifting:
10101101 << 3
Arithmetic Right
10101101 >> 3
(-1) >>> 29?
(x >>> 3) & ((1<<5)-1)? 5-bit integer, bits 3–7 of x.
Logical Right
10101100 >>> 3
• What is:
= ⌊x/2n⌋ (i.e., rounded down).
Last modified: Mon Sep 30 16:56:19 2019 CS61B: Lecture #14 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com