题目背景
在计算机的存储层次中,Cache(高速缓存)位于 CPU 与主存之间,常用于缓解 CPU 与主存之间的速度差异;RAM 断电后数据丢失,ROM 断电后数据不丢失,而 Cache 容量小、速度极快。
本题考察其中之一:直接映射(direct-mapped)Cache 的地址分解。
题目描述
主存按块大小 B 字节分块,Cache 共有 L 行,每行只能存放一个主存块。对于字节地址 addr:
- 它所在的主存块号(块地址)为 k=⌊Baddr⌋;
- 该块只能被放到 Cache 的第 index=kmodL 行;
- 为了区分会落到同一行的不同主存块,还需要记录标记 $tag = \left\lfloor \dfrac{k}{L} \right\rfloor = \left\lfloor \dfrac{addr}{B \times L} \right\rfloor$。
给定 B、L 以及一个字节地址 addr,请计算并输出它对应的 Cache 行号 index 与标记 tag。
输入格式
一行,三个整数 B,L,addr,相邻两个整数之间用一个空格分隔,分别表示块大小(字节)、Cache 行数、字节地址。
输出格式
一行,两个整数 index 与 tag,用一个空格分隔,行末输出换行符。
样例
样例 1
输入:
16 8 128
输出:
0 1
解释:k=⌊128/16⌋=8,index=8mod8=0,tag=⌊8/8⌋=1。
样例 2
输入:
1024 1024 1000000000
输出:
690 953
解释:k=⌊1000000000/1024⌋=976562,index=976562mod1024=690,tag=⌊976562/1024⌋=953。
数据范围
- 1≤B≤1024;
- 1≤L≤1024;
- 0≤addr≤109。
注意:tag 最大可能达到 109,请使用 64 位整数(long long)进行计算与输出。