# Bitmap结构在ENSToken里的应用

By [franx.eth](https://paragraph.com/@franx-2) · 2022-05-14

---

在ENSToken的合约里看到了Bitmaps的应用，在地址认领空投时用了Merkle树证明来check用户地址和认领数量，进而会对应一个Merkle的index，为了防止重复认领空投，合约里用了OpenZeppelin的Bitmaps库来做位图存储，地址认领成功后，就将对应的index在位图里存true，下次如果再来认领就会判断这个位图，如果为true时就返回错误，以此来防止重复认领空投。

    BitMaps.BitMap private claimed;
    /**
    * @dev Claims airdropped tokens.
    * @param amount The amount of the claim being made.
    * @param delegate The address the tokenholder wants to delegate their votes to.
    * @param merkleProof A merkle proof proving the claim is valid.
    */
    function claimTokens(uint256 amount, address delegate, bytes32[] calldata merkleProof) external {
        bytes32 leaf = keccak256(abi.encodePacked(msg.sender, amount));
        (bool valid, uint256 index) = MerkleProof.verify(merkleProof, merkleRoot, leaf);
        require(valid, "ENS: Valid proof required.");
        require(!isClaimed(index), "ENS: Tokens already claimed.");//认领过就revert
        
        claimed.set(index);//设置位图，表示当前index认领过空投
        emit Claim(msg.sender, amount);
    
        _delegate(msg.sender, delegate);
        _transfer(address(this), msg.sender, amount);
    }
    

普通的做法可以用mapping(uint256=>bool) hasClaimed来实现此功能，认领过就hasClaimed\[index\]=true，这样做每个index都要进行一下写storage操作，消耗较多的gas。可以采用位图来优化存储，因为uint256有256位，每位对应一个bool值，最多可以存储256个index，显然不够，因此可以将index拆分成n个256，存储到多个槽位，就变成mapping(uint256=>uint256) \_data结构来存储位图。

    struct BitMap {
       mapping(uint256 => uint256) _data;
    }
    function set(BitMap storage bitmap, uint256 index) internal {
        uint256 bucket = index >> 8;//右移8位，相当于除以256取整
        uint256 mask = 1 << (index & 0xff);
        bitmap._data[bucket] |= mask;
    }
    

上面代码的index&0xff相当于index对256取模，计算出余数，然后用1左移对应的余数位，表示要在256位中的哪一位写上1，就表示true，然后对\_data里对应槽位的数据做或运算，表示更新存储。除了第一次的bucket存储是写操作要消耗20000gas外，后面相同的bucket存储就是修改操作，消耗5000gas，显然比上面的那种方法节省gas。

例如：index=1000

index>>8=3，bucket=3

index&&0xff=232

1<<232，表示如下二进制整数

![](https://storage.googleapis.com/papyrus_images/0324001ba2ca22f8915e8d1d968866d205af6de8f2e16d60c0549d6572ed9de8.png)

再对bitmap.\_data\[bucket\]进行或运算，相当于将bitmap.\_data\[bucket\]值的第232位设置为1。

对应的get则相反，将bitmap.\_data\[bucket\]与mask做与运算，如果不为0，就表示这个位是1。

    function get(BitMap storage bitmap, uint256 index) internal view returns (bool) {
        uint256 bucket = index >> 8;
        uint256 mask = 1 << (index & 0xff);
        return bitmap._data[bucket] & mask != 0;
    }
    

位图结构对存储uint256=>bool的映射时可以节省gas cost，如果是address，可以uint256(uint160(addr))转为uint256后使用此结构。例如，记录某地址是否做过某事时就可以用Bitmaps。

---

*Originally published on [franx.eth](https://paragraph.com/@franx-2/bitmap-enstoken)*