Skip to content

Instantly share code, notes, and snippets.

@sdebnath
Created January 9, 2016 18:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sdebnath/f5e5ac98c4c275bb0178 to your computer and use it in GitHub Desktop.
Save sdebnath/f5e5ac98c4c275bb0178 to your computer and use it in GitHub Desktop.
Determine if string contains all unique characters using a bitmap
#include <stdio.h>
#include <string.h>
int is_unique(char* str) {
/*
* Bit check array for 256 values
* Rationale: 256 / 32 = 8. 32 for 32 bits in an integer
*/
int check[8] = {0};
int i, val, idx1, idx2;
int tmp;
for (i = 0; i < strlen(str); i++) {
/*
* To determine which bit is related to the val,
* we first divide the value by 8 to locate which "integer" * in the array of 8 we are dealing with
*/
val = (int)str[i];
idx1 = val / 32;
/*
* Once the first level map is located, now we need to
* determine which index in that integer corresponds to
* the value we are dealing with. We do by using the
* modulo operator: divide and get remainder, in this case
* divide by 32 since we have 32 bits in an integer
*/
idx2 = val % 32;
tmp = check[idx1];
if (tmp & (1 << idx2)) {
/* If we found a match, return immediately */
return 0;
} else {
/*
* If we didn't find a match, preare a fresh
* integer with the one bit set to where we need it.
* Then use the 'or' operator to set it in the map
*/
tmp |= (1 << idx2);
check[idx1] = tmp;
}
}
return 1;
}
int main() {
char *str1 = "abcdefgh";
printf(">> str1: %d\n", is_unique(str1));
char *str2 = "ello";
printf(">> str2: %d\n", is_unique(str2));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment