Sinisterly
upper-lower-case combinations with a bitmask - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Java, JVM, & JRE (https://sinister.ly/Forum-Java-JVM-JRE)
+--- Thread: upper-lower-case combinations with a bitmask (/Thread-upper-lower-case-combinations-with-a-bitmask)

upper-lower-case combinations with a bitmask - Deque - 05-06-2013

Hello HC.

I made the following code, because @noize requested for my archivecracker that for a given wordlist all upper-lower-case combinations could be checked too.
That means if you have the word "word", it should check:

Code:
word
Word
wOrd
WOrd
woRd
WoRd
wORd
WORd
worD
WorD
wOrD
WOrD
woRD
WoRD
wORD
WORD

How to produce these words?
If you want some exercise you can stop reading here, create your own code and come back to compare. Wink

I think a simple way doing this is using bitmasks as the title suggests.

Bitmask howto

What is a bitmask
Imagine you have the following binary number as information:
Code:
1101011

Now you want to check if a certain bit is set or not. So you specify what bit you want to check by making a bitmask:
Code:
0001000

This means the fourth bit shall be checked.

Using the bitwise operator AND you will get a result that is either 0 or has the value of your bitmask:

Code:
1101011 AND
0001000
-------------
0001000

Back to the task

We want to use binary numbers to encode whether a character in a word is upper or lowercase. 0 means lowercase, 1 means uppercase.

Examples:

Code:
wORd
0110
Word
1000

The advantage is that we just have to count in binary to get all possible combinations. For the word "word" we have four characters, so we have to count from 0 up to (2^4 - 1) and get the following numbers:

Code:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

That means the number of words we can produce can be calculated like this:

Code:
int numberOfCases = (int) Math.pow(2, word.length());

For every n (0 <= n < numberOfCases) we need the create the corresponding word with the help of a bitmask.

Example: We have the number 0110 and want to get word that belongs to it.
We start with the first character (at index because an array starts at 0) and want to know if it is upper- or lowercase.

That means we need a bitmask that looks like this for the first character:
1000

And like this for the second:
0100

And like this for the fourth:
0010

And like this for the last:
0001

So we calculate the bitmask for index i the following way:
Code:
int bitmask = (int) Math.pow(2, (length-1) - i);

Note: pow(2, (length-1) - i) can be simplified to pow(2, i) as it doesn't really matter if we generate the combinations from back to front or vice versa

Checking the bitmask and assigning the lower- or uppercase character at index i is done like this:

Code:
if ((bitmask & n) == bitmask) {
    modified[i] = Character.toUpperCase(originalWord[i]);
} else {
    modified[i] = Character.toLowerCase(originalWord[i]);
}

The operator & is the bitwise AND like I explained above.

Example:
Our index i is 2
We calculate our bitmask: 2^2 = 4
This is 0100 in binary

We check with the actual number that encodes our upper-lower-cases:
0100 AND
0110
-----
0100

The result is in this case 4 which is the value of our bitmask.
So we have to use an uppercase letter at index 2.

The source code
Code:
public class UpperLowerCombinator {

    public static void main(String[] args) {
        String word = "word";
        printAllCases(word);
    }

    private static void printAllCases(String word) {
        UpperLowerCombinator caser = new UpperLowerCombinator();
        for (String variant : caser.getAllCases(word)) {
            System.out.println(variant);
        }
    }

    private String[] getAllCases(String word) {
        int numberOfCases = (int) Math.pow(2, word.length());
        String[] variants = new String[numberOfCases];

        for (int i = 0; i < numberOfCases; i++) {
            variants[i] = getCase(i, word.toCharArray());
        }

        return variants;
    }

    private String getCase(int n, char[] originalWord) {
        int length = originalWord.length;
        char[] modified = new char[length];
        for (int i = 0; i < length; i++) {
            int bitmask = (int) Math.pow(2, i);
            if ((bitmask & n) == bitmask) {
                modified[i] = Character.toUpperCase(originalWord[i]);
            } else {
                modified[i] = Character.toLowerCase(originalWord[i]);
            }
        }
        return new String(modified);
    }

}


If you have any questions, post below.

Happy coding.
Deque

upper-lower-case combinations with a bitmask - Deque - 05-06-2013

Hello HC.

I made the following code, because @noize requested for my archivecracker that for a given wordlist all upper-lower-case combinations could be checked too.
That means if you have the word "word", it should check:

Code:
word
Word
wOrd
WOrd
woRd
WoRd
wORd
WORd
worD
WorD
wOrD
WOrD
woRD
WoRD
wORD
WORD

How to produce these words?
If you want some exercise you can stop reading here, create your own code and come back to compare. Wink

I think a simple way doing this is using bitmasks as the title suggests.

Bitmask howto

What is a bitmask
Imagine you have the following binary number as information:
Code:
1101011

Now you want to check if a certain bit is set or not. So you specify what bit you want to check by making a bitmask:
Code:
0001000

This means the fourth bit shall be checked.

Using the bitwise operator AND you will get a result that is either 0 or has the value of your bitmask:

Code:
1101011 AND
0001000
-------------
0001000

Back to the task

We want to use binary numbers to encode whether a character in a word is upper or lowercase. 0 means lowercase, 1 means uppercase.

Examples:

Code:
wORd
0110
Word
1000

The advantage is that we just have to count in binary to get all possible combinations. For the word "word" we have four characters, so we have to count from 0 up to (2^4 - 1) and get the following numbers:

Code:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

That means the number of words we can produce can be calculated like this:

Code:
int numberOfCases = (int) Math.pow(2, word.length());

For every n (0 <= n < numberOfCases) we need the create the corresponding word with the help of a bitmask.

Example: We have the number 0110 and want to get word that belongs to it.
We start with the first character (at index because an array starts at 0) and want to know if it is upper- or lowercase.

That means we need a bitmask that looks like this for the first character:
1000

And like this for the second:
0100

And like this for the fourth:
0010

And like this for the last:
0001

So we calculate the bitmask for index i the following way:
Code:
int bitmask = (int) Math.pow(2, (length-1) - i);

Note: pow(2, (length-1) - i) can be simplified to pow(2, i) as it doesn't really matter if we generate the combinations from back to front or vice versa

Checking the bitmask and assigning the lower- or uppercase character at index i is done like this:

Code:
if ((bitmask & n) == bitmask) {
    modified[i] = Character.toUpperCase(originalWord[i]);
} else {
    modified[i] = Character.toLowerCase(originalWord[i]);
}

The operator & is the bitwise AND like I explained above.

Example:
Our index i is 2
We calculate our bitmask: 2^2 = 4
This is 0100 in binary

We check with the actual number that encodes our upper-lower-cases:
0100 AND
0110
-----
0100

The result is in this case 4 which is the value of our bitmask.
So we have to use an uppercase letter at index 2.

The source code
Code:
public class UpperLowerCombinator {

    public static void main(String[] args) {
        String word = "word";
        printAllCases(word);
    }

    private static void printAllCases(String word) {
        UpperLowerCombinator caser = new UpperLowerCombinator();
        for (String variant : caser.getAllCases(word)) {
            System.out.println(variant);
        }
    }

    private String[] getAllCases(String word) {
        int numberOfCases = (int) Math.pow(2, word.length());
        String[] variants = new String[numberOfCases];

        for (int i = 0; i < numberOfCases; i++) {
            variants[i] = getCase(i, word.toCharArray());
        }

        return variants;
    }

    private String getCase(int n, char[] originalWord) {
        int length = originalWord.length;
        char[] modified = new char[length];
        for (int i = 0; i < length; i++) {
            int bitmask = (int) Math.pow(2, i);
            if ((bitmask & n) == bitmask) {
                modified[i] = Character.toUpperCase(originalWord[i]);
            } else {
                modified[i] = Character.toLowerCase(originalWord[i]);
            }
        }
        return new String(modified);
    }

}


If you have any questions, post below.

Happy coding.
Deque

RE: upper-lower-case combinations with a bitmask - Psycho_Coder - 05-06-2013

Thank you another great contribution to build better programmers.

RE: upper-lower-case combinations with a bitmask - Psycho_Coder - 05-06-2013

Thank you another great contribution to build better programmers.