Linuxから始める先端IT

Linuxから始める先端ITは現役大学生が綴り運営しているIT系情報ブログです。いろいろなニュースや情報をみなさんにお届けします。

基本情報技術者(FE)

ハッシュ表について

ハッシュ表とは、索引など高速に検索が必要な場合に利用されるデータ形式である。データを識別するキー値から、演算でデータの格納場所を求めることができる。問題のなかには、ハッシュ表に関する知識がなくても、単純に数値変換の計算問題として回答することができるものもある。

まず、55550を11進数とみなし10進数に変換すると、
5*11^4+5*11^3+5*11^2+5*11^1+0*11^0
=5*11*(11^3+11^2+11^1+11^0)
=55*(1331+121+11+1)
=55*1454
=80520

たとえば、これの下4桁のみが計算対象の場合、下4桁を抜き出す。
その0520に0.5を掛けると、
アドレス=0520×0.5=0260
その結果、アドレスは0260になる。

ハッシュ表でデータの格納場所を求める方法を図でしめす

hash_table

基数変換:ある進数から別の進数に置き換えること 

シフト演算について

シフト演算


シフト演算に関する話題である。シフト演算とは、シフト(桁ずらし)を行うことで演算を行うものである。
10進数の数値123を左に1桁シフトすると、1230となり10倍になる。同様に、2進数の数値110(=6)を左に1ビット分シフトすると、1100(=12)となり、2倍になる。2進数の数値110(=6)を左に2ビット分シフトすると、11000(=24)となり、4倍になる。つまり、2進数をnビット左にシフトすると、もとの数値の「2のn乗」倍になる。
1ビット左シフトするごとに2倍になるので、xを2ビット左シフトすると4倍の4xになる。
さらにこれにxを加えると
4x+x=5x
つまり5倍になる。

 例えば、x=0001(=1)として、1ビット左シフトすると、
y=0010(=2)となる。y=2xである。
xを2ビット左にシフトするとz=0100(=4)となる。z=4xである。
したがって、”レジスタの値を2ビット左にシフトして、xを加える”操作を行うと、
s=z+x=4x+x=5x
つまり5倍になる。

用語


あふれ(オーバーフロー):扱える数値範囲の最大値を超えてしまうこと。



最新コメント
QRコード
QRコード
記事検索
アクセスカウンター
  • 今日:
  • 昨日:
  • 累計:

PVグラフ

    UUグラフ