BitSet

کلاس BitSet کلاسی است که آرایه ای از بیت ها را شبیه سازی می کند و می توان از آن در الگوریتم های مختلفی مانند غربال اراتستن ، بزرگترین زیر مجموعه مشترک و … استفاده کرد ، به علاوه این کلاس عملگر های بیتی همچون AND , OR و غیره را نیز در اختیار ما قرار می دهد.

به صورت پیشفرض تمام خانه های BitSet صفر هستند. این کلاس از طریق مسیر java.util.BitSet قابل دستیابی است. برای استفاده از این کلاس می توانیم از یکی از سازنده های زیر استفاده کنیم.

BitSet()

این کلاس یک BitSet خالی ایجاد می کند و اندازه آن در طی زمان بر حسب نیاز افزایش می یابد.

BitSet(int nbits)

این کلاس یک BitSet با تعداد بیت های مورد نیاز ما ایجاد می کند که البته در طول زمان ممکن است اندازه آن نیز افزایش یابد. متد های مهم این کلاس در جدول زیر آمده اند :

متد کاربرد
and(BitSet other) بیت های BitSetفعلی را با بیت های BitSet دیگری AND می کند.
andNot(BitSet other) ابتدا بیت های BitSet دیگر را معکوس کرده و سپس با BitSet فعلی AND می کند. (یعنی AND(NOT B))
cardinality() تعداد بیت هایی که یک هستند را بر می گرداند.
clear() کل بیت ها را صفر می کند.
clear(int bitIndex) یک بیت خاص را صفر می کند.
clear(int from,int to) تمام بیت های داخل یک باز خاص (از اندیس from تا اندیس to) را صفر می کند.
equals(Object o) برابری BitSet با شی دیگری را بررسی می کند.
flip(int bitIndex) بیت مشخص شده در اندیس bitIndex را معکوس می کند.
flip(int from,int to) بیت های یک باز مشخص را معکوس می کند.
get(int index) مشخص می کند که بیت یک اندیس خاص صفر (false) است یا یک (true)
BitSet(int from,int to) یک زیر مجموعه از BitSet فعلی بر می گرداند.
intersetcts(BitSet other) اگر BitSet فعلی با BitSet دیگر حداقل یک بیت 1 (true) مشترک داشته باشد true بر می گرداند.
isEmpty() اگر BitSet هیچ بیت یکی نداشته باشد true بر می گرداند.
length() اندیس سمت راست ترین یک موجود در BitSet را بر می گرداند.
nexClearBit(int from) اندیس اولین بیت صفر بعد از اندیس from را بر می گرداند.
nextSetBit(int from) اندیس اولین بیت یک بعد از اندیس from را بر می گرداند.
or(BitSet other) BitSet فعلی را با BitSet دیگر OR می کند.
previousClearBit(int from) اندیس اولین بیت صفر قبل از اندیس from را بر می گرداند.
previousSetBit(int from) اندیس اولین بیت یک قبل از اندیس from را بر می گرداند.
set(int index) بیت مشخص در اندیس index را یک (true) می کند.
set(int from,int to) بیت های بازه from تا to را یک (true) می کند.
set(int index,boolean value) بیت موجود در اندیس index را بر اساس مقدار value مقداری دهی می کند.(true برای یک و false معادل صفر)
set(int from,int to,boolean value) تمام بیت های یک بازه مشخص را به مقدار value تغییر می دهد.
size() تعداد کل بیت های BitSet را نمایش می دهد.
toByteArray() معادل BitSet را به صورت آرایه ای از بایت ها بر می گرداند.
toLongArray() معادل BitSet را به صورت آرایه ای از Long ها بر می گرداند.
xor(BitSet other) BitSet فعلی را با BitSet دیگری xor می کند.

تبدیل String به BitSet

متاسفانه کلاس BitSet ابزاری برای تبدیل یک رشته صفر و یک به BitSet را ندارد و خودمان باید کد لازم برای این کار را به صورت زیر بنویسیم :

static void fromString(BitSet bs, String str)
{
    for (int i = 0; i < str.length(); i++)
    {
        if (str.charAt(i) == '1')
            bs.set(i, true);
    }
}

در کد بالا در داخل یک حلقه for به ازای هر کاراکتری از رشته str که 1 باشد اندیس متناظر با آن در BitSet را یک (true) می کنیم.

نمایش دودویی BitSet

متاسفانه کلاس BitSet ابزار مناسبی برای نمایش دودویی BitSet نیز در اختیار ما قرار نمی دهد و مجدداً خودمان باید کد لازم را بنویسیم ، کد زیر با داشتن تعداد بیت ها (nbits) یک String از روی بیت های BitSet می سازد و بر می گرداند.

static String toString(BitSet bs, int nbits)
{
    String result = "";
    for (int i = 0; i < nbits; i++)
    {
        if (bs.get(i))
        {
            result += "1";
        }
        else
        {
            result += "0";
        }
    }
    return result;
}

منطق کد بالا بسیار ساده است ، اگر بیت اندیس i در BitSet یک باشد یک 1 به انتهای رشته result اضافه می کنیم در غیر این صورت یک 0 به انتهای رشته اضافه می کنیم. با کمک دو متد بالا آماده ایم تا مثالی از کلاس BitSet مشاهده کنیم.

import java.util.BitSet;

public class BitSetDemo
{
    static void fromString(BitSet bs, String str)
    {
        for (int i = 0; i < str.length(); i++)
        {
            if (str.charAt(i) == '1')
                bs.set(i, true);
        }
    }
    static String toString(BitSet bs, int nbits)
    {
        String result = "";
        for (int i = 0; i < nbits; i++)
        {
            if (bs.get(i))
            {
                result += "1";
            }
            else
            {
                result += "0";
            }
        }
        return result;
    }
    public static void main(String[] args)
    {
        int nbits = 6;
        BitSet A = new BitSet(nbits);
        BitSet B = new BitSet(nbits);

        fromString(A, "110011");
        fromString(B, "100111");

        System.out.println("A :\t" + toString(A, nbits));
        System.out.println("B :\t" + toString(B, nbits));

        B.flip(0, 6);       //B=Not(B)
        System.out.println("B :\t" + toString(B, nbits));

        A.or(B);            //A=A OR B
        System.out.println("A :\t" + toString(A, nbits));

        A.and(B);           //A=A AND B
        System.out.println("A :\t" + toString(A, nbits));

        A.set(0);           //A[0]=1
        System.out.println("A :\t" + toString(A, nbits));

        A.set(4, 6, true);  //A[4]=1,A[5]=1
        System.out.println("A :\t" + toString(A, nbits));

    }
}

A :	110011
B :	100111
B :	011000
A :	111011
A :	011000
A :	111000
A :	111011

در کد بالا ابتدا دو BitSet خالی به نام A و B ایجاد کردیم و سپس با متد های کمکی ()fromString آن دو را مقدار دهی کرده و برای اطمینان آن ها را کمک متد کمی ()toString چاپ کردیم. سپس بیت های اندیس 0 تا 6 B را با کمک متد ()flip معکوس و بعد با کمک متد or بیتست A را با بیتست دوم OR کردیم. سایر خطوط نیز مشابه هستند و همراه آن ها در کد توضیحات کافی ارائه شده است.