circuit for finding the index of first zero entry in a binary string

finding the index of first zero entry in a binary string:

Input: binary string ($0$'s and $1$'s)

Output: index of first zero entry

Can you give a circuit for finding the index of first zero entry in a binary string with minimum depth and polynomial many processors?

1) Is this problem in $AC_0$?

2) Is this problem in $NC_1$?

Can point me at references?

• 1) Yes. ​ 2) Yes. ​ ​ ​ What do you want the output to be on all-1 inputs? ​ ​ ​ ​ ​ ​ ​ ​
– user12859
May 18 '17 at 4:49
• How can you build a circuit of AC_0? If all 1 inputs then nothing outputs.
– GOLD
May 18 '17 at 4:58
• Start with an example: ​ If the input length is 6, then what positions of [first zero entry] will cause an output whose middle bit is 1? ​ ​ ​ ​
– user12859
May 18 '17 at 5:56
• @RickyDemer Can you explain more clearly ?
– GOLD
May 18 '17 at 6:43
• Would [a first zero entry being at index 0] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 1] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 2] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 3] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 4] cause an output whose middle bit is 1? ​ Would [a first zero entry being at index 5] cause an output whose middle bit is 1? ​ ​ ​ ​
– user12859
May 18 '17 at 6:47