# Java 7ms O(n) solution using bit manipulation with explanation

• Thanks to the idea from http://bookshadow.com/weblog/2016/09/04/leetcode-utf-8-validation/

I wrote the Java version.

The basic idea is:

1. First determine if a n-bytes character start with '0', '110', '1110' or '11110' and find out n.
3. Do the same thing to next character until the end of the array data.
``````public class Solution {
public boolean validUtf8(int[] data) {
int[] masks = new int[]{0x0, 0x80, 0xE0, 0xF0, 0xF8};
int[] bits = new int[]{0x0, 0x0, 0xC0, 0xE0, 0xF0};
int start = 0;
while(start < data.length) {
int n;
// start from a character
// determine its number of bytes (n-bytes)
for(n = 4; n >= 0; n--) {
if((data[start] & masks[n]) == bits[n]) break;
}
// if not beginning with '0', '110', '1110', '11110'
// or not have enough length
// return false
if(n == 0 || start + n > data.length ) return false;
for(int j = 1; j < n; j++) {
// check if followed by n-1 bytes beginning with '10'.
if((data[start+j] & 0xC0) != 0x80) return false;
}
// continue with next character
start += n;
}
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.