#454. 直接映射 Cache 的地址分解

直接映射 Cache 的地址分解

题目背景

在计算机的存储层次中,Cache(高速缓存)位于 CPU 与主存之间,常用于缓解 CPU 与主存之间的速度差异;RAM 断电后数据丢失,ROM 断电后数据不丢失,而 Cache 容量小、速度极快。

本题考察其中之一:直接映射(direct-mapped)Cache 的地址分解

题目描述

主存按块大小 BB 字节分块,Cache 共有 LL 行,每行只能存放一个主存块。对于字节地址 addraddr

  • 它所在的主存块号(块地址)为 k=addrBk = \left\lfloor \dfrac{addr}{B} \right\rfloor
  • 该块只能被放到 Cache 的第 index=kmodLindex = k \bmod L 行;
  • 为了区分会落到同一行的不同主存块,还需要记录标记 $tag = \left\lfloor \dfrac{k}{L} \right\rfloor = \left\lfloor \dfrac{addr}{B \times L} \right\rfloor$。

给定 BBLL 以及一个字节地址 addraddr,请计算并输出它对应的 Cache 行号 indexindex 与标记 tagtag

输入格式

一行,三个整数 B,L,addrB, L, addr,相邻两个整数之间用一个空格分隔,分别表示块大小(字节)、Cache 行数、字节地址。

输出格式

一行,两个整数 indexindextagtag,用一个空格分隔,行末输出换行符。

样例

样例 1

输入:

16 8 128

输出:

0 1

解释:k=128/16=8k = \lfloor 128/16 \rfloor = 8index=8mod8=0index = 8 \bmod 8 = 0tag=8/8=1tag = \lfloor 8/8 \rfloor = 1

样例 2

输入:

1024 1024 1000000000

输出:

690 953

解释:k=1000000000/1024=976562k = \lfloor 1000000000/1024 \rfloor = 976562index=976562mod1024=690index = 976562 \bmod 1024 = 690tag=976562/1024=953tag = \lfloor 976562/1024 \rfloor = 953

数据范围

  • 1B10241 \le B \le 1024
  • 1L10241 \le L \le 1024
  • 0addr1090 \le addr \le 10^{9}

注意:tagtag 最大可能达到 10910^{9},请使用 64 位整数(long long)进行计算与输出。